当${j=10}$时,刚好三个物品都能装下,它们的总值为14,即${f(2,10)=14}$
第三行的结果如下:
w v i 0 1 2 3 4 5 6 7 8 9 10
2 6 0 0 0 6 6 6...而看一下i-1的边界问题,有的书与博客为了解决它,会添加第0行,全部都是0,然后i再往下挪。其实我们也可以添加一个${-1}$行。...([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)
1.4 递归法解01背包
由于这不是动态规则的解法,大家多观察方程就理解了:
function knapsack(...2.2 问题分析:
最简单思路就是把完全背包拆分成01背包,就是把01背包中状态转移方程进行扩展,也就是说01背包只考虑放与不放进去两种情况,而完全背包要考虑 放0、放1、放2...的情况,
这个k当然不是无限的...总而言之,如果放当前物品i的话,它的状态就是它自己"i",而不是上一个"i-1"。