带重复的背包 - 阵列解决方案

Knapsack with repetition - array solution

我试图理解 class 中给我的背包算法,具体如下伪代码。

这是我尝试编写的代码:

//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) 总是在循环的最后一次迭代中给出 "index out of bounds" 错误。 items 数组从索引 0 开始,但 i 从 1 开始。为什么我们从索引 1 开始?我是否误解了变量?

我得到:

The object problem includes the maximum weight of the knapsack (problem.knapsack) and an array of available items (problem.items). Each item is an object with a weight and value attribute (problem.items[i].weight and problem.items[i].value). Both of these functions should return an array of selected items. The items in the returned array should also have weight and value attributes.

您想查看 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 编号。您的代码有不同的约定,其中项目编号从 0items.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);

顺便说一句,作业要求你做的比伪代码做的更多。伪代码仅计算您可以通过最佳打包实现的总价值。该作业要求您 return 一组用于最佳包装的物品。