重复背包 - 数组解决方案

Question

我想了解在课堂上给予我的背包算法，特别是下面的伪代码。

这是我尝试编写它：

//Init array 
var solution = []; 
var items = problem.items; 
var sackSize = problem.knapsack; 

solution[0] = 0; 
for(var k = 1; k <= sackSize; k++) 
{ 
    var loot = 0; 
    for(var i = 1; i <= items.length; i++) 
    { 
     if(k >= items[i].weight) 
     { 
      loot = Math.max(loot, items[i].value) 
     } 
    } 
    solution[k] = loot; 
} 

这没有意义，我因为if(k >= items[i].weight)总是给人一种“索引超出界限”错误上的最后一次迭代循环。 items数组从0开始，但i从1开始。为什么我们从索引1开始？我误解了变量吗？

我给出：

对象问题包括背包 （problem.knapsack）的最大重量和可用项（problem.items）的阵列。 每个项目都是一个具有重量和价值属性 （problem.items [i] .weight和problem.items [i] .value）的对象。这两个 函数都应返回一个选定项目的数组。 返回数组中的项目也应该具有权重和值属性。

Answer 1

你想看看items数组的每个元素。第一个元素是items[0]，最后一个元素是items[items.length-1]。

因此，你应该改变行

for (var i = 1; i <= items.length; i++) 

这样：

for (var i = 0; i < items.length; i++) 

现在items[i].weight将是最后一次迭代有效。

那么为什么伪代码说以下？

for (i = 1; i <= n; i++) { 

好了，伪代码是用在哪些项目是从1到n编号数学约定。您的代码有一个不同的约定，其中项目编号从0到items.length-1。

这不是你的代码和伪代码之间的唯一区别。例如，您正在编写k >= items[i].weight而不是k ≥ W[i]。此外，您使用var表示法声明局部变量。这是因为你的代码是一个实际的实现。伪代码是一种数学抽象。

伪代码中的抽象思想是逐个查看项目，数学表达为W[1]到W[n]。在您的代码中，第一项是items[0]，最后一项是items[items.length-1]。您必须相应地编写for声明。

啊，但背包容量呢？我们是否也必须更改该循环索引？答案是不。在这里，我们正在处理具有不同含义的不同索引。我们不是在数组中查找项目，而是创建一个新数组，我们想要使用从0到sackSize之间的值进行索引。 solution[k]的价值是容量为k的背包的最佳包装。

为了更清楚些，我建议你声明solution阵列像这样：

var solution = new Array(sackSize+1); 

顺便说一句，分配要求你做多的伪代码在做什么。伪代码只计算您可以通过最优打包实现的总值。该任务要求您返回用于优化打包的项目数组。