0

在本教程中,我们之前已经使用Greedy方法讨论了分数背包问题。我们已经证明Greedy方法为分数背包提供了最佳解决方案。但是,本章将介绍0-1背包问题及其分析。 在0-1背包中,物品不能被打破,这意味着小偷应该将物品作为一个整体或应该离开它。这就是将其称为0-1背包的原因。 因此,在0-1背包的情况下,x i 的值可以是0或1,其中其他约束保持不变。 0-1背包无法通过贪婪方法解决。贪心方法无法确保最佳解决方案。在许多情况下,贪婪方法可以提供最佳解决方案。 以下示例将建立我们的声明。

例1

让我们考虑背包的容量是W = 25,项目如下表所示。
项目 A B C D
利润 24 18 18 10
重量 24 10 10 7
不考虑每单位重量的利润(p i / w i ),如果我们采用贪婪的方法来解决这个问题,那么第一项将选择一个,因为它将在所有元素中贡献最大 i 利润。选择项目A后,将不再选择项目。因此,对于这套给定的项目,总利润为24。然而,通过选择项目B和C可以实现最佳解决方案,其中总利润为18 + 18 = 36。

例2

在该示例中,不是基于总体益处选择项目,而是基于比率 p i / w i 来选择项目。让我们考虑背包的容量是 W = 60,项目如下表所示。
项目 A B C
价格 100 280 120
重量 10 40 20
比率 10 7 6 使用贪婪方法,选择第一项A。然后,选择下一个项目B。因此,总利润为100 + 280 = 380。但是,通过选择项目BC可以实现此实例的最佳解决方案,其中总利润为280 + 120 = 400
因此,可以得出结论,贪婪方法可能无法给出最优解。 要解决0-1背包问题,需要动态编程方法。

问题陈述

一个小偷正在抢劫一家商店,并且可以携带一个最大的 i 重量的W到他的背包里。有n项目和i th项目的重量是w i 和选择此项目的利润是p i 。小偷应该带些什么东西?

动态规划方法

*是最优解的最高编号项。那么*S ' = S - {i}W - w i 美元的最优解,并且值为解决方案SV i *加上子问题的值。 我们可以用下面的公式表达这个事实:定义c [i,w ]作为项目的解决方案1,2,...,i和max i 妈妈的体重w。 该算法采用以下输入
  • 最大 i 妈妈体重W
  • 物品数量n
  • 两个序列v = >w = >

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w] 
要从表中推导出的一组项目,从c [n,w ]开始,并向后追踪最佳值的来源。 如果 c [i,w ] = c [i-1,w ] ,则项目i不是解决方案的一部分,我们继续跟踪c [i -1,w ]。否则,项目i是解决方案的一部分,我们继续跟踪c [i-1,w-W ]

分析

该算法取θ( n w )次,因为table c 具有( n + 1)。( w + 1)个条目,其中每个条目需要θ(1)时间来计算。