algorithm - 为什么交换背包的元素顺序会导致相同的解决方案？

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] 表示 < em>i - 第 item.

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