poj 1018 Communication System

題意：

某公司要建立一套通信系統，該通信系統需要n種設備，而每種設備分別可以有m1、m2、m3、...、mn個廠家提供生產，而每個廠家生產的同種設備都會存在兩個方面的差別：帶寬bandwidths 和 價格prices。

現在每種設備都各需要1個，考慮到性價比問題，要求所挑選出來的n件設備，要使得B/P最大。

其中B為這n件設備的帶寬的最小值，P為這n件設備的總價。

分析：此題目可用多種方法求解，DP 、 搜索 、貪心 、三分法

這裡講dp的思路。

我們定義狀態dp 【i】【j】 表示選擇了前 i 個寬帶其容量為 j 的最小費用。

很容易得到轉移方程 ：dp【i】【j】=min（dp【i】【j】，dp【i-1】【k】+p）；

注意選擇 j 的時候的大小情況。

順便提供一下貪心的思路。（正確性未知）

從初始的第一個要選的寬帶的每一個開始，每次向下貪心選擇一個總的 B/P 的最大值，找出其中最大的既為答案。有興趣的可以驗證一下正確性！

dp代碼：

#include 
#include 
#include 
using namespace std;
const int inf = 0x3f3f3f3f;
int dp[120][1200];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)  //初始化
        {
            for(int j=0; j<1100; j++)
                dp[i][j]=inf;
        }
        for(int i=1; i<=n; i++)   //dp
        {
            int num;
            scanf("%d",&num);
            for(int j=1; j<=num; j++)
            {
                int p,b;
                scanf("%d%d",&b,&p);
                if(i==1)
                {
                    dp[1][b]=min(dp[1][b],p);
                }
                else
                {
                    for(int k=0; k<1100; k++)
                    {
                        if(dp[i-1][k]!=inf)
                        {
                            if(k<=b)
                                dp[i][k]=min(dp[i][k],dp[i-1][k]+p);
                            else
                                dp[i][b]=min(dp[i][b],dp[i-1][k]+p);
                        }
                    }
                }
            }
        }
        double ans=0;
        for(int i=0; i<1100; i++)
        {
            if(dp[n][i]!=inf)
            {
                double k=(double)i/dp[n][i];
                if(k>ans)
                    ans=k;
            }
        }
        printf("%.3lf\n",ans);
    }
    return 0;
}