P5365 转移写错了 然后看题解改对了 但是不理解转移的设计
AC代码here
我不理解的是为什么枚举重量要放在外边一层:
for(ull j = qb; j >= 1; --j) {
for(ull x = 1; x <= k[i] && c[i] * x <= j; ++x) {
dp[j] = max(dp[j], dp[j - c[i] * x] * x);
}
}
而不是放在最内层
for(int j = 1; j <= k[i]; ++j) {
for(int x = qb; x >= c[i] * j; --x) {
dp[x] = max(dp[x], dp[x - c[i] * j] * j);
}
}
但是P2347重量就放在了最内层,
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= a[i]; ++j) {
for(int k = W; k >= w[i]; --k) {
dp[k] = max(dp[k], dp[k - w[i]]);
}
}
}