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

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

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

我对动态规划方法感到困惑:为什么不计算每个项目的(值(value)/重量)的分数并选择重量小于袋子剩余重量的最佳分数的项目？

最佳答案

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

考虑

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

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

关于algorithm - 为什么要对 0/1 背包进行动态规划？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47196985/