POJ 1018 DP入门

POJ 1018 DP入门

http://blog.csdn.net/xiaoxiaoluo/article/details/7787168      代码完全参考这个blog  刚开始学习DP真是很艰难阿,  题目如下:

 

We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

Output

Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

Sample Input

Sample Output

这个题目也可以不用dp来做,不过现在既然练习的是dp这里就只给出dp如何做

思路是这样的,因为我们要找最大的B/sum P那么无论对于哪一个B ,该状态下的sumP 应该最小, 然后 枚举所有的最终态,找到最大的B/sumP 既是正确答案,

有一点小问题要注意一下 输出的问题,输出浮点数的时候不要用%.nlf  用%.nf前者在一些编译器上会概率性出错  尤其是POJ23333333

我们用dp[i][j]来表示选前i件物品 且 最小带宽为j的情况下的最小sumP

这样状态转移方程就可以表示为

 

根据这个状态转移方程 其实可以理解这个算法了,就是遍历所有的从 0 —-maxb的dp数组然后对当前选的组别进行dp  由于带宽不是连续的 因此从 0—maxb 中 有很多无意义的带宽值 这些值就用 -1 这个不能被正常计算取到的值进行标记 ,然后 选第一组物品的时候 对dp数组进行初始化赋值,从第二轮开始,每一轮dp都是先看这个数组里这里的dp[i][minb]是否算过了,如果没有算过,就直接用上一步dp[i-1][j]的值进行处理 否则 要比较当前的值和 dp[i-1][j]+p[k] 的大小 ,取小的那个

 

代码如下:

上面的状态转移方程和这里用的字母都一致对应

发表评论

电子邮件地址不会被公开。 必填项已用*标注

3 × 1 =