WholeItemKnapsackFiller { @Complexity(value = "O(nW)", explanation = "We go over the all items for each value of weight in 1..W") public Set<Integer> fill(int size, int... weights) { final int[][] memory = new int[size + 1][]; final int[] indices = new int[size + 1]; for (int i = 0; i < size + 1; i++) { memory[i] = new int[weights.length + 1]; memory[i][0] = 0; indices[i] = -1; } for (int i = 0; i < weights.length + 1; i ++) { memory[0][i] = 0; } for (int weight = 1; weight <= size; weight ++) { for (int i = 1; i <= weights.length; i ++) { if (weights[i - 1] > weight) { memory[weight][i] = memory[weight][i - 1]; } else { final int current = weights[i - 1] + memory[weight - weights[i - 1]][i - 1]; if (current > memory[weight][i - 1]) { indices[weight] = i; memory[weight][i] = current; } else { memory[weight][i] = memory[weight][i - 1]; } } } } final Set<Integer> result = new HashSet<>(); int weight = memory[size][weights.length]; while (weight > 0) { final int index = indices[weight] - 1; result.add(index); weight -= weights[(index)]; } return result; }  @Complexity(value = "O(nW)", explanation = "We go over the all items for each value of weight in 1..W") Set<Integer> fill(int size, int... weights);  }
@Test public void testFillingTornKnapsack() throws Exception { final Set<Integer> indices = fill(0, 1, 2, 3, 4); assertThat(indices, is(empty())); }
@Test public void testReplacingTheContent() throws Exception { final int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; final Set<Integer> indices = fill(10, weights); assertThat(sum(weights, indices), is(10)); assertThat(indices, is(not(empty()))); assertThat(indices, hasSize(4)); assertThat(indices, contains(0, 1, 2, 3)); }
@Test public void testReversedOrder() throws Exception { final int[] weights = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; final Set<Integer> indices = fill(10, weights); assertThat(sum(weights, indices), is(10)); assertThat(indices, is(not(empty()))); assertThat(indices, hasSize(1)); assertThat(indices, contains(0)); }
@Test public void testMixed() throws Exception { final int[] weights = {1, 7, 2, 6, 3, 5, 4}; final Set<Integer> indices = fill(10, weights); assertThat(sum(weights, indices), is(10)); assertThat(indices, is(not(empty()))); assertThat(indices, hasSize(3)); assertThat(indices, contains(0, 1, 2)); }