algorithm - 为什么要对 0/1 背包进行动态规划？

Question

我查看了很多资源，还this问题，但仍然很困惑为什么我们需要动态规划来解决 0/1 背包问题？

问题是:我有 N 个项目，每个项目的值为 Vi，每个项目的权重为 Wi。我们有一袋总重量 W。如何选择项目以在重量限制下获得最佳总值(value)。

我对动态规划方法感到困惑:为什么不只计算每件元素的(值(value)/重量)分数，然后选择重量小于袋中剩余重量的最佳分数的元素？

Answer 1

对于基于分数的方法，您可以轻松找到反例。

考虑

W=[3, 3, 5]
V=[4, 4, 7]
Wmax=6

您的方法给出了最优值 Vopt=7(我们取自 7/5 > 4/3 以来的最后一项)，但取前两项给出我们 Vopt=8。