0/1背包问题：动态规划方法

本文概述

• 背包问题
• 0/1背包问题
• 0/1背包问题的示例
• 背包问题算法

背包问题

背包基本上是指背包。一袋给定的容量。

我们想在你的行李中装n件物品。

• 第一项价值为美元, 重量为磅。
• 尽可能承受有价值的负载, 但不能超过W磅。
• vi wi W是整数。

W ≤ capacity
Value ← Max

输入：

• 容量背包
• 重量列表（数组）及其相应的值。

产出：最大化利润并最小化生产能力。

背包问题, 我们必须以最大的价值包装背包, 以使物品的总重量不大于背包的容量。

背包问题可以进一步分为两个部分：

1.小背包：小背包问题可以通过贪婪策略解决, 而0/1问题不是。

它不能用动态编程方法解决。

0/1背包问题

在这个物品中不能被打破, 这意味着小偷应该把这个物品当作一个整体或者应该离开。这就是为什么它被称为0/1背包问题。

• 每个项目都已采取或未采取。
• 不能取一小部分物品或一件以上的物品。
• 贪婪方法无法解决此问题, 因为它可以填补背包容量。
• 贪婪方法不能确保最佳解决方案。

0/1背包问题的示例

示例：背包可以容纳的最大重量为11。有五种选择。下表列出了它们的权重和值：

此处的[i, j]项将为V [i, j], 如果最大容量为j, 则可使用项目的前“ i”行获得的最佳值。我们从初始化和第一行开始。

V [i, j] = max {V [i - 1, j], vi + V [i - 1, j -wi]

V [3, 7]的值计算如下：

V [3, 7] = max {V [3 - 1, 7], v3 + V [3 - 1, 7 - w3]
         = max {V [2, 7], 18 + V [2, 7 - 5]} 
         = max {7, 18 + 6}
         = 24

最后, 输出为：

背包中物品的最大值是40（右下角的条目）。现在可以将动态编程方法编码为以下算法：

背包问题算法

KNAPSACK (n, W)
 1. for w = 0, W
 2. do V [0, w] ← 0
 3. for i=0, n
 4. do V [i, 0] ← 0  
 5. for w = 0, W
 6. do if (wi≤ w & vi + V [i-1, w -  wi]> V [i -1, W])
 7. then V [i, W] ← vi + V [i - 1, w - wi]
 8. else V [i, W] ← V [i - 1, w]