poj 1018 Communication System

Communication System

Description

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

1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110

Sample Output

0.649

通信系统

描述

我们收到了一份来自Pizoor Communications Inc.的特殊通信系统的订单。该系统由几个设备组成。对于每个设备，我们可以从几个制造商中自由选择。两个制造商生产的相同设备最大带宽和价格不同。

总带宽(B)是指通信系统中所选设备的最小带宽，总价格(P)是所有所选设备的价格之和。我们的目标是为每个设备选择一个制造商，以最大化B/P。

输入

输入文件的第一行包含单个整数t(1≤t≤10)，测试用例的数量，后面是每个测试用例的输入数据。每个测试用例以包含单个整数n(1≤n≤100)(通信系统中的设备数量)的一行开始，后面有n行，格式如下:第I行(1≤I≤n)从mi(1≤mi≤100)开始，mi(1≤mi≤100)是第I个设备的制造商数量，其后是同一行的mi对正整数，每对分别表示设备的带宽和价格，对应一个制造商。

输出

您的程序应该为每个测试用例生成一行代码，其中包含一个数字，这是测试用例的最大可能B/P值。将输出的数字四舍五入到小数点后的3位。

Sample Input

1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110

Sample Output

0.649

题意：

目前有一个公司需要购进宽带设备，每种设备有多款机器供选择，每种设备都需购进一台，现给出每台设备的带宽p与价格q，要求选择设备的最小带宽min(p)/add(q)（其中min(p)表示所有购进设备中最小的带宽，add(q)表示所有购进设备的价格之和）为最大，并求出该值。

非常明显这个问题可以进行分解，分解如下：

设dp[i][j]为前i组带宽为j的最小价格和，那么状态转移方程为dp[i][j]=min{dp[i][j] , dp[i-1][k]+q}，表示dp[i][j]为在两种情况中取最小值：

1.j正好为最小带宽，dp[i][j]就为前i组带宽为j的价格和

2.之前的带宽k为最小带宽，价格为之前价格再加上q

代码：

#include
#include 
using namespace std;
const int inf = 0x3f3f3f3f;
int a[120][1100];

//状态转移方程：dp[i][j] = min( dp[i][j] , dp[i-1][k]+q ) 
//dp[i][j]表示前i组带宽为j的最小价格 
int main()
{
    int n;
    cin>>n; 
    while(n--)
    {
        int m;
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<1100;j++)
            {
                a[i][j]=inf;
            } 
        } 
        for(int i=1;i<=m;i++)
        {
            int num;
            cin>>num;
            for(int j=0;j            {
                int p,q;
                cin>>p>>q;
                if(i==1)
                {
                    a[i][p]=min(a[1][p],q);
                }
                else
                {
//之所以从0遍历到1200：
//1.预估带宽最大到1200
//2.保证所有的带宽与对应的最小价格都被存到二维数组中,最后所求最小价格即为a[3][min带宽] 
                    for(int k=0;k<1100;k++)
                    {
                        if(a[i-1][k]!=inf)
                        {
                            if(k<=p)
                            {
                                a[i][k]=min(a[i][k],a[i-1][k]+q);
                            }
                            else
                            {
                                a[i][p]=min(a[i][p],a[i-1][k]+q); 
                            }
                        }
                    }
                }
            }
        }
        double res=0;
        for(int i=0;i<1100;i++)
        {
            if(a[m][i]!=inf)
            {
                double temp = (double)i/a[m][i];
                if(temp>res)
                {
                    res=temp;
                }
            }
        }
        printf("%.3lf\n",res);
    }
    return 0;
}