看不懂背包解决办法

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

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

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

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