We now solved the Knapsack problem in two different ways: using top-down and bottom-up dp. However, both those solutions only give the value of the solution.

Here we will see how we can actually reconstruct the set of items that are taken for the top-down solution.

In order to be able to build the solution, we will remember for each state what was the action that lead us to the optimal value. Then we will trace back those actions from the initial state \((0, C)\).

In this problem there are two actions: skip an item and take an item. To make the code more readable but not require to create a lot of objects in memory, we will simply define those as two integers with the names SKIP and TAKE.

Also, we will need to keep track of which action lead to each of the states. We can do this with a matrix \(action\) of size \(n\) by \(C + 1\).

static int SKIP = 0, TAKE = 1;
static Integer[][] action;

Our previous code ended with:

  ...
  // memorize the value of state (i, c)
  memo[i][c] = Math.max(skip, take);
  return memo[i][c]
}

This is where we know what is the best action. It corresponds to the maximum between \(skip\) and \(take\). So if \(skip \geq take\) then we know that the action to do is SKIP and otherwise it is TAKE. We can easily change it to set the best action as follows:

  ...
  // memorize the value of state (i, c) and set action
  if(skip >= take) {
    memo[i][c] = skip;
    action[i][c] = SKIP;
  } else {
    memo[i][c] = take;
    action[i][c] = TAKE;
  }
  return memo[i][c];
}

To build the set of items we start from state \((0, C)\) and check what is the value of \(action[0][C]\). If it is SKIP then we know that item \(0\) is not in the optimal solution. Thus we ignore it and go to state \((1, C)\). Otherwise, if it is TAKE, then we know item \(0\) is in the optimal solution. We add it to the list of items in the solution and go to state \((1, C - w_0)\). We repeat this process until we either run out of items or out of space in the knapsack.

More generally, if we are in state \((i, c)\) then:

• if \(action[i][c] = SKIP\) we go to state \((i + 1, c)\)
• if \(action[i][c] = TAKE\) we go to state \((i + 1, c - w_i)\) and add \(i\) to the list of items taken.

static LinkedList<Integer> buildSolution() {
  int i = 0;
  int c = C;
  LinkedList<Integer> taken = new LinkedList<>();
  while(i < n && c >= 0) {
    if(action[i][c] == TAKE) {
      taken.add(i);
      c -= w[i];
    }
    i += 1;
  }
  return taken;
}

For the bottom-up solution the idea is the same. Try to do it by yourself and submit it to the task below to make sure that it is correct.