I am trying to solve the classic 0/1 knapsack problem with a slight variant where we are asked to return the maximum value + the list of included items.
Input items = [[1,2],[4,3],[5,6],[6,7]] where items[i][0] is the value and items[i][1] denotes the weight capacity = 10
Output [10,[1,3]] // maximum value is 10 when items at index 1 and 3 are included
When we are simply asked to return the maximum value, I understand the brute-force, top-down and tabular approaches and I get it that it takes O(n*w) time and space to store and compute these many states.
As I work through this specific question that asks us to return the list of items as well, I wonder if my Top-Down DP approach takes O(nnw) time [the brute force takes O(n2^n)] . I looked at a sample tabular approach solution where we build the table and then follow the decision sequence to get the list of items. This doesn't change the TC and SC = O(nw). I am wondering if something similar is possible with top-down.
I assume that my below code runs for O(nnw) because writing to the result in the base case takes O(n) time. Is it possible to achieve O(n*w) to output the required result using top-down approach? If yes, how?
Here's my code :
Please note that the below code is passing for the majority of the test cases, but doesn't pass them all - so I know that something might be off, but my overall approach seems correct.
public static List<List<Integer>> knapsackProblem(int[][] items, int capacity) {
List<List<Integer>> result = new ArrayList<>();
int n = items.length;
int[][] memo = new int[n+1][capacity+1];
for (int i = 1; i < n + 1; i++) {
Arrays.fill(memo[i], -1);
}
knapsackHelper(0, items, capacity, new ArrayList<Integer>(), result, memo);
return result;
}
private static int knapsackHelper(int index, int[][] items, int curCapacity, List<Integer> itemIndices, List<List<Integer>> result, int[][] memo) {
if (index == items.length || curCapacity == 0) {
int totalValue = 0;
for (int itemIndex : itemIndices) {
totalValue += items[itemIndex][0];
}
if (result.isEmpty()) {
result.add(Arrays.asList(new Integer[]{totalValue}));
result.add(new ArrayList<>(itemIndices));
} else if (result.get(0).get(0) < totalValue) {
result.set(0, Arrays.asList(new Integer[]{totalValue}));
result.set(1, new ArrayList<>(itemIndices));
}
return totalValue;
}
if (memo[index+1][curCapacity] != -1) {
return memo[index][curCapacity];
}
int valueWhenIncluded = Integer.MIN_VALUE;
if (items[index][1] <= curCapacity) {
itemIndices.add(index);
valueWhenIncluded = knapsackHelper(index+1, items, curCapacity-items[index][1], itemIndices, result, memo);
itemIndices.remove(itemIndices.size()-1);
}
int valueWhenExcluded = knapsackHelper(index+1, items, curCapacity, itemIndices, result, memo);
return memo[index+1][curCapacity] = Math.max(valueWhenIncluded, valueWhenExcluded);
}