0/1背包问题（动态规划方法） _动态规划

本文概述

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

背包问题背包基本上是指背包。一袋给定的容量。
我们想在你的行李中装n件物品。

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

W ≤ capacityValue ← 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

文章图片
最后, 输出为：

文章图片
【0/1背包问题（动态规划方法）】背包中物品的最大值是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]