本文共 1925 字,大约阅读时间需要 6 分钟。
题意:一套通讯系统由一些设备组成,每种设备由不同的供应商供应,每个供应商供应的同种设备有各自的带宽(bandwidth)和价格(prices)。通讯系统的带宽(B)指的是组成该系统的所有设备的带宽的最小值,通讯系统的价格(P)指的是组成该系统的所有设备的价格之和。求最大的 (B / P)。
算法:动态规划,由前i-1个供应商得到前i个供应商的情况 定义 dp[i][j]=k 为前i个供应商、B=j时最小的P为k 那么,已知前i-1个供应商的情况,如何求i的情况? 定义min_b为所有供应商中最小的B,max_b为最大的B 对第i个供应商的每个设备j 对dp[i-1][k] (min_b <= k <= max_b) v[i][j][0] // 第i个供应商第j个设备的带宽 v[i][j][1] // 第i个供应商第j个设备的价格 t = min(k,v[i][j][0]) // 判断是否选择第i个供应商第j个设备 if (dp[i][t] < dp[i-1][k] + v[i][j][1]) { dp[i][t] = dp[i-1][k] + v[i][j][1] } 示例说明: 1 3 3 100 25 150 35 80 25 2 120 80 155 40 2 100 100 120 110 分别选择: 1: 150 35 2: 155 40 3: 120 110 B=120 P=185 B/P=0.649#include#include #include #include using namespace std;double dp[120][1200]; // dp[i][j] = k: 前i个供应商所能提供的设备,当最小带宽为j时,价格的最小和为k int v[120][120][2]; // vp[i][j][0]、vp[i][j][1]: 分别表示第i个供应商的第j个设备的带宽和价格 int d[120]; // dp[i] = j: 第i个供应商有j个相同的设备 void init(){ for (int i=0; i<=120; i++) { for (int j=0; j<=1200; j++) { dp[i][j] = INT_MAX; } }}void solve(int n,int min_b, int max_b){ // 枚举每个供应商 for (int i=2; i<=n; i++) { // 枚举第i个供应商的所有设备 for (int j=1; j<=d[i]; j++) { // 枚举i-1个供应商的所有情况,其min(B)的范围是(min_b,max_b),当然此范围是稍微放大的 for (int k=min_b; k<=max_b; k++) { int t = min(k,v[i][j][0]); if (dp[i][t] > dp[i-1][k]+v[i][j][1]) { dp[i][t] = dp[i-1][k]+v[i][j][1]; } } } }}int main(){ int t,n; int b,p; cin >> t; for (int i=0; i > n; int min_b = INT_MAX; int max_b = -1; for (int j=1; j<=n; j++) { cin >> d[j]; for (int k=1; k<=d[j]; k++) { cin >> v[j][k][0] >> v[j][k][1]; min_b = min(min_b,v[j][k][0]); max_b = max(max_b,v[j][k][0]); if (j == 1) { dp[1][v[j][k][0]] = min(double(v[j][k][1]),dp[1][v[j][k][0]]); } } } solve(n,min_b,max_b); for (int j=min_b; j<=max_b; j++) { if (dp[n][j] > 0 && 1.0*j/dp[n][j] > ans) { ans = 1.0*j/dp[n][j]; } } printf( "%.3f\n" , ans ) ; }}
转载地址:http://urlbb.baihongyu.com/