讨论/技术交流/为什么多重背包不能用完全背包的优化思路?/
为什么多重背包不能用完全背包的优化思路?

完全背包的优化思路:

f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...)

f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,...)

下式+w代换上式max中第二项起的所有项可得f[i][j] = max(f[i-1][j], f[i][j-v]+w)

为什么多重背包不能用这样的优化思路?多重背包不是同样有

f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...)

f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,...)

吗?

1
共 4 个回复

因为你不知道 f[i][j-v] 是不是已经用完了第 ii 种物品。如果用完了,f[i][j] 就不能从 f[i][j-v] 转移过来了。

1

感觉一楼是对的,二楼的那种说法存疑

恍然大悟,感谢您很精确地解答了我的问题!

把省略号补完,完全背包最后一项都是f[i1][jmodv]f[i-1][j\mod v],而多重背包分别是f[i1][jkv]f[i-1][j-kv]f[i1][j(k+1)v]f[i-1][j-(k+1)v],根本对不齐.
另外多重背包可以使用单调队列做到和完全背包一样的复杂度.

1