poj 1018 Communication System

╰+攻爆jí腚メ 2022-08-26 14:19 98阅读 0赞

题意：

某公司要建立一套通信系统，该通信系统需要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 <cstdio>
    #include <cstring>
    #include <algorithm>
    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;
    }