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);
  }
0

There are 0 best solutions below