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

Question

我试图理解 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.

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);

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

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

Knapsack with repetition - array solution

javascript

algorithm

knapsack-problem

dynamic-programming