在维基百科中，Knapsack 的算法如下：
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
我在网上找到的所有示例的结构都是相同的。
我无法理解的是这段代码如何考虑到最大值可能来自smaller背包？例如。如果背包容量为 8，则最大值可能来自容量 7 (8 - 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]
（如果您设置了，则 else 条件在递归形式中是多余的T(i,j) = -infinity对于每个j < 0).
这个想法是详尽的搜索，您从一个元素开始，有两种可能性：添加或不添加。
您检查这两个选项，并选择其中最好的一个。
由于它是递归完成的 - 您可以有效地检查将元素分配给背包的所有可能性。
请注意，维基百科中的解决方案基本上是相同递归公式的自下而上的解决方案
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
