本文概述
背包问题
背包基本上是指背包。一袋给定的容量。
我们想在你的行李中装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]
