玄关 刚学背包 求助背包简单题
  • 板块灌水区
  • 楼主CNCAGN
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/11/4 09:08
  • 上次更新2023/11/4 10:58:42
查看原帖
玄关 刚学背包 求助背包简单题
65161
CNCAGN楼主2023/11/4 09:08

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]]);
		}
	}
}
2023/11/4 09:08
加载中...