Knapsack Problem In JavaScript

The knapsack problem provides us with an array of items. Each item has a weight and a value. We are also given a knapsack capacity which is the maximum weight that the knapsack can hold. Our task is to figure out the highest value of items that we can fit in the knapsack.

For example, if we have three items. The first has a value of 5 and a weight of 2. The second has a value of 2 and a weight of 3. The third has a value of 6 and a weight of 5. The knapsack weight capacity is 5. In this case the maximum value would be 7 because we can carry the first and second items which have a higher combined value than if we chose to take the third item. The first two items have a combined weight of 5, so we can take both. The third item has a weight of 5 but its value is only 6 so it would be better to take the first two items instead.

One way to approach this problem is to create a 2D array where the rows are each item and the columns are each metric of weight from 0 to the knapsack capacity. We start with a row of all 0s at the top representing no items being chosen. As we work down the rows, we are calculating the maximum possible value for each weight as we add each item. For example, the second row calculates the maximum by adding just the first item. The third row calculates the maximum possible with the first and second items. The forth row calculates the maximum possible with the first, second and third items. And so forth.

If we use our previous example the chart would look like this (the first number is the item’s value and the second is the item’s weight).

The max weight capacity is 5 so we create a column for 0 to 5. We make a row of 0s signifying no items being added. Next we add the first item (value:5, weight:2) and go through each weight increment. If the weight is 0 or 1 we can’t carry this item so we mark those values as zero. For any weight 2 or greater we can add that item, so we mark the max value as 5. Then we add the next item (value:2, weight:3). This item can’t be carried with a capacity of 0 or 1 so those columns are marked as 0. When we get to the weight of 2, we still have the option of taking the first item so we mark this column as 5. When we get to the weight of 3 we have the choice of taking either the first or second item. The first item has a higher value so we choose that and mark the column as the value of the first item. When we get to the weight of 5, we can now carry both the first and second items with a combined value of 7. When we get to the last item (value:6, weight:5) there is no weight were we can carry the item and have the value be greater than just taking the first two items instead, so we keep the same maximum values from the prior row.

Code

To code this, first we want to create our 2D array made up of only 0s. The number of columns is the capacity + 1 to account for our 0 column. The numbers of rows is the length of items + 1 to account for our initial row of 0s. We can do this by first creating an empty array. Then we use a for loop to create new arrays (rows) and use the fill method to initialize the row values to 0. We then push the row arrays to our original empty array.

Next we are going to use a nested for loop to iterate through our 2D array and calculate the maximum total value for each weight increment as we add each new item. We start the index of the outer loop at 1 because our first row is kept at all 0s to represent no items be added. We also add 1 to the items length to account for initial 0 row. Inside of the outer loop we add two variables to represent the current value and the current weight. Because of that initial row of 0s, we are setting the variables to i minus 1 so it starts at the first item. In this example we have the value at index 0 of each item and the weight at index 1.

The inner loop is going to iterate through each column of weight within the max capacity. We start the index at 0 and add 1 to the max capacity to account for the initial weight of 0. We can only add an item if its weight is less than the current column weight, so we use an “if else” conditional to check that. If the current weight is greater, we take the value from the previous row in that column and set it as the value in the current row. If the current weight is less than the column weight, we want check to see if we will get a greater max value by adding the current item to the knapsack or if we would be better off with the previous max value of that column. This can be done by using JavaScript’s math max function.

We calculate the value of adding the new item by taking the current column weight and subtracting the weight of the current item. This takes us to the column in the current row that shows the max value of the current column weight minus the weight of the current item. In our previous example, if we are on the last item (value:6, weight:5) and on column weight 5, we subtract the current item’s weight (5) which brings us to column weight 0 for this item, which has a max value of 0. We add the current item’s value (6) which gives us a total of 6. We pass this number and the max total from the previous row (7) into the math max function to give us the highest total. We then assign the highest value to the 2D array.

Once we iterate through all the items we now have our greatest max as the last element of the 2D array. We can return this as MaxTotals[items.length][capacity].

Here is the final solution.