传送门 // 题意是中文就不重复了…. 思路也很简单就是个普普通通的01背包类型. 就说几个坑点…..
1: 这个保证了只精确到小数点后2两位， 也就是我们可以通过将钱扩大100倍使得下标允许范围内的… 所以范围要大一点….. 这一点在题目中没有说…
2: 题目虽然说的是”单项物品的价值”， 但是这里的项指的是一类……. 所以每一类的价钱要分开统计……
然后就是普通的01背包了…. 这种题太坑了，描述不请….
AC Code
const int maxn = 3e6+5; int dp[maxn], w[40]; void solve() { db m; int n; while(~scanf("%lf%d", &m, &n)) { if (!n) break; int id = 0; int tot = int(m*100); for (int i = 1 ; i <= n ; i ++) { int num; scanf("%d", &num); db s = 0, s1 = 0, s2 = 0, s3 = 0, c; char a; int flag = 1; while(num--) { getchar(); a = getchar(); getchar(); scanf("%lf", &c); if (a < 'A' || a > 'C') flag = 0; if (a == 'A') s1 += c; if (a == 'B') s2 += c; if (a == 'C') s3 += c; s += c; } if (s1 > 600 || s2 > 600 || s3 > 600) flag = 0; if (flag && s <= 1000.0) w[++id] = int(s*100); getchar(); } Fill(dp, 0); for (int i = 1 ; i <= id ; i ++) { for (int j = tot ; j >= w[i] ; j --) { dp[j] = max(dp[j] ,dp[j-w[i]] + w[i]); } } printf("%.2f\n", 1.0*dp[tot]/100); } }