DP - Knapsack, build the solution

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.


Knapsack with solution

Put all the pieces that we discussed above together and write a solution for the Knapsack problem that is able to print the items that should be taken.

Input

  • One line with two integers \(C\) and \(n\) giving the knapsack capacity and the number of items respectively.
  • \(n\) lines each with two integers \(w\) and \(v\) giving the weights and the values of each of the items.

Output

The first line should contain a single integer with the maximum value that can be achieved.

The second line should contain integers separated by single spaces giving the indexes (0 indexed) of the items taken in your solution.

Any solution will be accepted if several optimal solutions exist.

Constraints

  • \(1 \leq C, n, v, w \leq 2000\)

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2


Max file size: 1.0MB
Allowed extensions: .java, .cpp, .py

Information

Author(s) François Aubry
Deadline No deadline
Submission limit No limitation

Sign in