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

本文概述

背包问题

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

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

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

输入:

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

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

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

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

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

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


0/1背包问题

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

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

0/1背包问题的示例

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

0/1背包问题示例:

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

0/1背包问题示例:
V [i, j] = max {V [i - 1, j], vi + V [i - 1, j -wi]
0/1背包问题的示例
0/1背包问题的示例

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背包问题的示例

最后, 输出为:

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]

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?