无法理解背包解决方案

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  

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

Answer 1

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

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

1. 0-1背包问题：在这里，物品是不可分割的，你要么拿一件物品，要么不拿。可以用动态规划法求解<代码>//这就是你面临的问题
2. 分数背包问题：现在不要关心这个问题

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

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

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

用数学的口吻说：

为了使用动态规划解决这个问题，我们建立了一个表，每个可用项目一行，从0到W的每个权重一列。我们需要仔细识别子问题，

然后，子问题将是计算V[k，w]，即在一个大小为w的背包中为Sk={标记为1，2，…k的项目}找到一个最优解（给定容量w和项目1，…，k可达到的最大值）

该算法仅查找背包中可能携带的最大值，即V[n，W]中的值，以了解使该值最大的项目，这将是另一个主题。

我真的希望这个答案能帮助你。我有一个pp演示，它将与您一起填写表格，并逐步向您展示算法。但我不知道如何将其上载到stackoverflow。如果需要帮助，请告诉我。

Answer 2

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

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]

（如果为每个<代码>j设置<代码>T（i，j）=-无穷大，则else条件在递归形式中是多余的

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

因为它是递归完成的——你有效地检查了将元素分配到背包的所有可能性。

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