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
我的代码
动规的一道简单题，要求B/P的最大值，因为B、P都是分别可变化的，可以固定B来求最小P。dp方程为dp[i][j]=dp[i-1][j]+min(device[i].p[t])。其中dp指在选择第i个设备时，想要达到j的带宽所需要的最少花费；device[i].p[t]指第i个设备的第t的供应商给出的价格。
求第i个设备达到带宽j的花费，显然是在前i-1个设备的基础上加上这次选择的设备，只要找到所有带宽大于等于j的设备的花费的最小值就可以了。如果找不到这样的设备，说明在选择第i个设备时带宽已经达不到j了，此时min的值为无穷大。
最后只要对所有的带宽进行求B/P，找出最大值即可。
#include<stdio.h>
#include<string.h>
const int inf=0x3f3f3f3f;
struct device
//记录每一个i个设备所有供应商给出的带宽和价格
{
int num;
int b[101];
int p[101];
device()
{
num=0;
}
}dev[101];
int n;
int dp[101][1000];
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (int i=0;i<n;i++)
{
scanf("%d",&dev[i].num);
for (int j=0;j<dev[i].num;j++)
{
scanf("%d%d",&dev[i].b[j],&dev[i].p[j]);
}
}
for (int i=0;i<1000;i++)
{
int min=inf;
for (int j=0;j<dev[0].num;j++)
{
if (dev[0].b[j]>=i)
{
if (dev[0].p[j]<min)
{
min=dev[0].p[j];
}
}
}
dp[0][i]=min;
}
for (int i=1;i<n;i++)
{
for (int b=0;b<1000;b++)
{
int min=inf;
for (int j=0;j<dev[i].num;j++)
{
if (dev[i].b[j]>=b)
{
if (dev[i].p[j]<min)
{
min=dev[i].p[j];
}
}
}
dp[i][b]=dp[i-1][b]+min;
}
}
double ans=0;
for (int b=0;b<1000;b++)
{
if (ans<(1.0*b/dp[n-1][b])) ans=(1.0*b/dp[n-1][b]);
}
printf("%.3f\n",ans);
}
return 0;
}另一种dp思路
dp[][]数组含义相同，但是处理方式不一样。方程dp[i][k] = min(dp[i][k],dp[i-1][j]+price)。如果bandwidth <= j，那么k = bandwidth；反之，k = j.直接看方程可能不是很明白，可以结合代码来看。
for(int k=0;k<M;k++){ //枚举带宽
if(band >= k) dp[i][k] = min(dp[i][k],dp[i-1][k]+price); //寻找最小的带宽
else dp[i][band] = min(dp[i][band],dp[i-1][k]+price);
}对于一个设备的带宽bandwidth，只有其大于等于我们遍历的带宽k时，它才能被采用，此时将不采用这个设备的总花费dp[i][k]和采用这个设备的总花费dp[i-1][k]+price比较，取小的。如果带宽小于k，则比较不选择对应的是dp[i][band]，取值为不选择这个设备的总花费dp[i][band]和选择了的总花费dp[i-1][k]+price的较小值。
代码如下
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int const inf = 0x7f7f7f7f;
int const N = 100;
int const M = 1200;
int n,m,band,price,dp[N+10][M+10];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<=n;i++){
for(int j=0;j<M;j++)
if(i == 0) dp[i][j] = 0;
else dp[i][j] = inf;
}
for(int i=1;i<=n;i++){ //总共有n个设备，每个设备挑一个，并且使他们的B/P最小。
scanf("%d",&m);
for(int j=1;j<=m;j++){
scanf("%d%d",&band,&price);
for(int k=0;k<M;k++){ //枚举带宽
if(band >= k) dp[i][k] = min(dp[i][k],dp[i-1][k]+price); //寻找最小的带宽
else dp[i][band] = min(dp[i][band],dp[i-1][k]+price);
}
}
}
double ans = 0;
for(int i=1;i<M;i++)
ans = max(ans,i*1.0/dp[n][i]);
printf("%.3f\n",ans);
}
return 0;
}反思
虽然感觉两种算法复杂度差不多，但是总觉得我的想法实在是太憨憨了。