本文共 1342 字,大约阅读时间需要 4 分钟。
标签:01背包
/* 找出符合报销条件的发票后,01背包裸题(N: 符合条件的发票数量total, V:报销额度Q)。 注意:(1)单项物品不能超过600元,而不是单个。如A:310 A:320,那A项物品为630元,不能报销。 (2)Q的处理(模板中会用到Q)。*/#include#include #include using namespace std;const int maxn = 3000000 + 5;int dp[maxn], value[35];int main(){ int N; double q; while(scanf("%lf %d", &q, &N) && N) { int Q = q * 100; int total = 0; while(N--) //找出可以报销的发票 { int m, flag = 0; char s; double price, a = 0.0, b = 0.0, c = 0.0; scanf("%d", &m); for(int i = 0; i < m; i++) { scanf(" %c:%lf", &s, &price); //%c前有一个空格 if(s == 'A') a += price * 100; else if(s == 'B') b += price * 100; else if(s == 'C') c += price * 100; else {flag = 1; break;} } if(a + b + c > 100000 || a > 60000 || b > 60000 || c > 60000) flag = 1; if(flag) continue; else value[total++] = a + b + c; } memset(dp, 0, sizeof(dp)); //ZeroOnePack template for(int i = 0; i < total; i++) for(int j = Q; j >= value[i]; j--) //Q = q * 100 dp[j] = max(dp[j], dp[j - value[i]] + value[i]); printf("%.2f\n", dp[Q] / 100.0); } return 0;}
转载地址:http://zikxi.baihongyu.com/