Knapsack with repetition - array solution

Question

I am trying to understand a knapsack algorithm given to me in class, specifically the following pseudocode.

enter image description here

This was my attempt to code it:

//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;
}

This doesn't make sense to me because if(k >= items[i].weight) always gives an "index out of bounds" error on the last iteration of the loop. The items array starts at index 0 but i starts at 1. Why are we starting at index 1? Am I misinterpreting the variables?

I am given:

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.

It is common in pseudo codes to iterate from 1 to n rather than 0 to n-1. Just because the pseudo code iterates from 1 to n does not mean your code also has to iterate from 1 to n especially when you know that array index starts at 0. — wookie919
@wookie919 so do you think the solution is not dependent on it starting at 1? — Deekor

Michael Laszlo Michael Laszlo · Accepted Answer · 2015-04-24T07:18:49

You want to look at each element of the items array. The first element is items[0] and the last element is items[items.length-1].

Therefore, you should change the line

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

to this:

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

Now items[i].weight will be valid on the last iteration.

So why does the pseudocode say the following?

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

Well, the pseudocode is using a mathematical convention in which items are numbered from 1 through n. Your code has a different convention in which items are numbered from 0 through items.length-1.

That's not the only difference between your code and the pseudocode. For example, you're writing k >= items[i].weight instead of k ≥ W[i]. Also, you're declaring local variables with the var notation. That's because your code is a practical implementation. The pseudocode is a mathematical abstraction.

The abstract idea in the pseudocode is to look at the items one by one, which is expressed mathematically as considering W[1] through W[n]. In your code, the first item is items[0] and the last one is items[items.length-1]. You must write the for statement accordingly.

Ah, but what about the knapsack capacity? Do we have to change that loop index as well? The answer is no. Here we're dealing with a different index that has a different meaning. Instead of looking up items in an array, we're making a new array that we want to index with values from 0 through sackSize. The value of solution[k] is an optimal packing for a knapsack of capacity k.

To make this clear, I suggest that you declare the solution array like this:

var solution = new Array(sackSize+1);

By the way, the assignment is asking you to do more than the pseudocode is doing. The pseudocode only computes the total value that you can achieve with an optimal packing. The assignment is asking you to return an array of items used in an optimal packing.

Knapsack with repetition - array solution

1 Answers