无法理解背包的解决方案 [英] Can not understand knapsack solutions

问题描述

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

In wikipedia the algorithm for Knapsack is as follows:

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  

和它是我在网上找到的所有实例相同的结构。
我不能理解的是，它如何code考虑到这一事实，也许最大的价值来源于较小背包？例如。如果背包容量为8，那么也许最大的价值来自于产能7（8 - 1）。
 我找不到任何地方的逻辑来考虑，也许最大的价值来自于一个小背包。这是错误的想法？

And it is the same structures on all examples I found online.
What I can not understand is how does this code take into account the fact that perhaps the max value comes from a smaller knapsack? E.g. if the knapsack capacity is 8 then perhaps max value comes from capacity 7 (8 - 1).
I could not find anywhere logic to consider that perhaps the max value comes from a smaller knapsack. Is this wrong idea?

推荐答案

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

The Dynamic Programming solution of knapsack is basically recursive:

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）=负无穷大每个 J＆LT; 0 ）。

我们的想法是穷举搜索，你从一个元素开始，你有两种可能性：添加，还是没有。
你检查这两个选项，并选择最好的那些。

The idea is exhaustive search, you start from one element and you have two possibilities: add it, or don't.
You check both options, and chose the best of those.

既然是递归完成 - 你有效地检查所有的可能性，将这些元素的背包

Since it is done recursively - you effectively checking ALL possibilities to assign the elements to the knapsack.

注意，在维基百科的溶液基本上是相同的递归式从下往上的溶液

Note that the solution in wikipedia is basically a bottom-up solution for the same recursive formula

这篇关于无法理解背包的解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！