Knapsack without repetition

Similarly to the previous problem, we have a knapsack with a specified capacity, a number of items with different weight and value, and we want to select a subset of them that would fit in the knapsack maximizing its value. The difference is that now we are not allowed to put in the knapsack copies of the same item. For this reason this problem is also known as 0/1 knapsack.

If we keep a dynamic programming approach, the solution won't be too different to the previous one, however we'll need to store the results for all subproblems in a bidimensional array and the process of generating a new subsolution is going to be a bit more complex.

The idea is that we have a row for each family of subproblems having up to the actual number of items we can choose from.

Zeroth row is there just to simplify the algorithm, being quite obvious that a knapsack containing zero or one element chosen from no item is going to always have a weight of zero.

First row is only marginally more interesting. We check the first item, as soon as its weight matches the capacity of a (sub)knapsack, we assign its value to that subsolution, an then al the other subsolutions on its right would have the same value, since we have no other items available.

It is from second row that we have a more clear view on the problem complexity, since for a generic position in it we have to ensure the capacity of the current knapsack in the subproblem would be optimally filled by the available items.

Let's see a test case to help us to figure out how to work it out.

public void testWithouRepetition() {
 int[] weights = new int[] { 2, 3, 4, 6 };
 int[] values = new int[] { 9, 14, 16, 30 };

 assertThat(Knapsack.withoutRepetition(values, weights, 10), is(46));
}

The table with all the subsolutions for our problem would be:

[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]
[ 0,  0,  9,  9,  9,  9,  9,  9,  9,  9,  9]
[ 0,  0,  9, 14, 14, 23, 23, 23, 23, 23, 23]
[ 0,  0,  9, 14, 16, 23, 25, 30, 30, 39, 39]
[ 0,  0,  9, 14, 16, 23, 30, 30, 39, 44, 46]

Notice that, zeroth column is an all-zero because whichever is the number of items available, having zero as capacity of the current sub-knapsack will lead to a no-item-selected solution. First column is again filled with zeroes, but for a different reason, there is no item with a weight 1.
In the first row we use only the first item available, the one with weight 2 and value 9. From the second cell on, we can put its value in it.
In the second row, we can put only {2, 9} in cell (2, 2). Next to the right, (2, 3), we could put {2, 9} or {3, 14}. The latter wins. Since (2, 5) on, we can put both items, so the value stored in these cells is 23.
And so on.

Here is how I have modified the algorithm seen in the previous post to adapt it to this slightly different problem:

public static int withoutRepetition(int[] values, int[] weights, int weight) {
   assert (values.length == weights.length); // 1

   int[][] results = new int[values.length + 1][weight + 1]; // 2
   for(int i = 1; i < results.length; ++i) { // 3
      for(int j = 1; j < results[i].length; ++j) { // 4
         results[i][j] = results[i - 1][j]; // 5
         if(weights[i - 1] > j) // 6
            continue;
         int candidate = results[i - 1][j - weights[i - 1]] + values[i - 1]; // 7
         if(candidate > results[i][j])
            results[i][j] = candidate;
      }
   }

   return results[values.length][weight];
}

1. A minimal checking to ensure no funny stuff in input. For each value should be available the correlated weight.
2. Core of the dynamic programming algorithm. A table that is going to contain all the subsolutions is created. The following double for loop will fill it up and in the bottom right cell we'll find the solution.
3. Row 0 is not affected, since we know that it has to contain just a bunch of zeroes.
4. Column 0, for each row, is not affected since, again, we just want a zero in it.
5. The current element is initialized with the value contained in the cell in row above, same column.
6. If the weight of the item associated with the current row is bigger than the capacity for the current subsolution, there is not much to do, just skip to the next iteration.
7. Otherwise, let's check if considering the new element in the knapsack will bring to a better solution. We make room for it in the knapsack, considering the best solution in the row above that has enough room for it, and add its value.

On GitHub you will see that my Java class Knapsack now has also the method to calculate the "without repetition" variation of the problem. And a test case for it has been added to the associated JUnit class.