algorithm - 看不懂背包解决办法

Question

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

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)。
我找不到任何逻辑来考虑最大值可能来自较小的背包。这是错误的想法吗？

Answer 1

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

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 设置 j < 0，则 else 条件在递归形式中是多余的)。

这个想法是穷举搜索，你从一个元素开始，你有两种可能性:添加它，或者不添加它。
您检查两个选项，然后选择其中最好的一个。

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

注意维基百科中的解法基本上是同一个递归公式自下而上的解法