为什么用动态规划解决0/1背包问题？

Question

3

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

问题是：我有N个物品，每个物品的价值为Vi，每个物品的重量为Wi。我们有一个总重量为W的袋子。如何选择物品以获得超过重量限制的最佳总价值。

我对动态规划方法感到困惑：为什么不只计算每个物品的（价值/重量）分数，并选择具有最佳分数且重量小于袋子剩余重量的物品？

- Jay Joshi

4个回答

2

正如其他答案所指出的那样，你的方法存在边界情况。

为了更好地解释递归解决方案，并可能更好地理解它，我建议您采用以下思路：

对于每个“subsack”

1. 如果我们没有合适的元素，则没有最佳元素 2. 如果我们只有一个合适的元素，则最佳选择是该元素 3. 如果我们有多个合适的元素，则取每个元素并计算其“subsack”的最佳拟合。最佳选择是具有最高价值的元素/ subsack组合。

这种算法之所以有效，是因为它涵盖了所有可能的合适元素组合，并找到了价值最高的组合。

相反，直接的解决方案是不可能的，因为问题是NP难问题。

- Sklivvz

1

只需要看这个反例：

Weight 7, W/V pairs (3/10),(4/12),(5/21)

- MBo

1

贪心算法在存在单位比率情况下会失败。例如，考虑以下示例：

n=1 2，P=4 18，W=2 18，P/W=2 1

背包容量为18

根据贪心算法，它将考虑第一件物品，因为它的P / W比率更大，因此总利润将为4（因为在插入第一件物品后，容量减少到16，无法在第一件物品之后插入第二件物品）。

但实际答案是18。

因此，在0/1背包问题中有多个边角情况，贪心算法无法给出最优解，这就是为什么我们使用动态规划的原因。

- anupam691997

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- algrid · Accepted Answer

作为使用分数的方法，你很容易找到一个反例。

考虑以下情况：

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

你的方法可以得到最优值Vopt=7（我们选择最后一项，因为7/5 > 4/3），但是选择前两项可以得到Vopt=8。