1

在维基百科中，背包的算法如下： 

for i from 1 to n do  
  for j from 0 to W do  
    if j >= w[i] then  
      T[i, j] := max(T[i-1, j], T[i-1, j-w[i]] + v[i]) [18]  
    else  
      T[i, j] := T[i-1, j]  
    end if  
  end for  
end for

我在网上找到的所有示例的结构都相同。
我无法理解的是这段代码如何考虑到最大值可能来自较小的背包这一事实？例如，如果背包容量为 8，那么最大值可能来自容量 7 (8 - 1)。
我找不到任何逻辑来考虑可能最大值来自较小的背包。这是错误的想法吗？

4

2 回答 2

5

背包的动态规划解基本上是递归的：

T(i,j) = max{ T(i-1,j) ,         T(i-1,j-w[i]) + v[i] }
       //      ^                         ^
       //  ignore the element       add the element, your value is increase
       //                           by v[i] and the additional weight you can
       //                           carry is decreased by w[i]

（如果T(i,j) = -infinity为 each设置 else 条件在递归形式中是多余的j < 0）。

这个想法是详尽的搜索，你从一个元素开始，你有两种可能性：添加或不添加。
您检查了这两个选项，并选择了其中最好的一个。

由于它是递归完成的 - 您有效地检查了将元素分配给背包的所有可能性。

请注意，维基百科中的解决方案基本上是相同递归公式的自下而上的解决方案

于 2013-01-03T10:47:49.837 回答
4

如我所见，您误解了背包的概念。在我们到达代码部分之前，我将在这里详细描述。

首先，有两个版本的问题：

  1. 0-1背包问题：这里的物品是不可分割的，你要么拿一个，要么不拿。并且可以用动态规划来解决。//and this one is the one yo are facing problems with
  2. 分数背包问题：现在不关心这个了。

对于第一个问题，您可以将其理解为：

给定一个最大容量为W的背包，以及由n 个物品组成的集合S每个物品i都有一些权重wi和收益值bi （所有wi 和W都是整数值）。

那么，如何包装背包以实现包装物品的最大总价值？

在数学口中：

在此处输入图像描述

并使用动态规划解决这个问题我们建立了一个表格V[0..k, 0..W]，其中每个可用项目一行，每个权重一列，从0到W。我们需要仔细识别子问题，

然后，子问题将是计算V[k,w]，即 在大小为wSk= {items labeled 1, 2, .. k}的背包中找到最佳解决方案（给定容量w和项目1，...，k可实现的最大值）

所以，我们找到了这个公式来解决我们的问题： 在此处输入图像描述

该算法只找到背包中可以携带的最大可能值，即V[n,W]中的值。要知道使该最大值的物品，这将是另一个话题。

我真的希望这个答案对您有所帮助。我有一个 pp 演示文稿，它会与您一​​起填写表格并逐步向您展示算法。但我不知道如何将它上传到stackoverflow。让我知道是否需要任何帮助。

于 2013-01-03T16:05:59.323 回答