上外国网站用什么dns/百度推广代理怎么加盟

题意：某公司要建立一套通信系统，该通信系统需要n种设备，而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：带宽bandwidths 和 价格prices。现在每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的n件设备，要使得B/P最大。其中B为这n件设备的带宽的最小值，P为这n件设备的总价。

思路：觉得是dp，但是写不出来，借鉴的别人的。首先看了（http://blog.csdn.net/y990041769/article/details/23735949），并理解了他的思路，但是发现其中假设带宽最大为1200在题目中并没有体现，所以这种方法应该是有问题的。后来又看了（http://blog.csdn.net/lyy289065406/article/details/6676781）的枚举加剪枝的方法。

#include <stdio.h>
#include <string.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define N 105
#define M 1200
#define INF 0x3fffffff
int dp[N][M];
int n,m,T;
int main(){scanf("%d",&T);while(T--){int i,j,k,v,p;double res = 0;scanf("%d",&n);for(i = 1;i<=n;i++)for(j = 1;j<M;j++)dp[i][j] = INF;for(i = 1;i<=n;i++){scanf("%d",&m);for(j = 1;j<=m;j++){scanf("%d %d",&v,&p);if(i == 1)dp[1][v] = p;elsefor(k = 1;k<M;k++){if(dp[i-1][k]!=INF){if(k <= v)dp[i][k] = min(dp[i][k],dp[i-1][k]+p);elsedp[i][v] = min(dp[i][v],dp[i-1][k]+p);}}}}for(i = 1;i<M;i++)res = max(res,(double)i/dp[n][i]);printf("%.3lf\n",res);}return 0;
}