为什么交换背包的物品顺序会导致相同的解决方案？

Question

据我所知，背包问题使用动态规划来根据每个项目的前一项找到它的最佳解决方案。该假设假设解决方案取决于项目的顺序。为什么最终的解决方案不取决于顺序？

Answer 1

不是。背包问题的动态规划解不依赖于前面的项目。

在考虑是否将物品放入背包时，我们只需要考虑选择物品前后背包的剩余容量即可。所以我们遍历所有可能的剩余容量并选择最好的一个。

dp[i][c] = max(dp[i-1][c+w[i]] + v[i], dp[i-1][c])

其中dp[i][c]表示考虑第i个项目后背包剩余容量等于c的最大可能值。w[i]表示第i个物品的重量（或体积），v[i]表示第i个物品的价值。

没有必要按顺序考虑项目。按顺序考虑项目只是为了方便。您还可以考虑以相反的顺序或随机顺序选择项目。