To write a code for solving the 0-1 knapsack problem by implementing the recursive approach.

Remember that this is a recursive top-down approach, thus it repeatedly computes the same subproblems for an exponential runtime complexity (2ⁿ). The following code snippet solves this problem using a recursive approach:

public int recursiveAux(int W, int weights[], int values[], int n) {
  if (n == 0 || W == 0)
    return 0;
  if (weights[n - 1] > W)
    return recursiveAux(W, weights, values, n - 1);
  return Math.max(values[n - 1] +
   recursiveAux(W - weights[n - 1], weights, values, n - 1),
   recursiveAux(W, weights, values, n - 1));
 }

The following diagram of tree shows the recursion for n and W, with inputs values[] = {10, 20, 30} and weights[] = {1, 1, 1}:

Since problems are evaluated again, this has the overlapping subproblems property. When we have a recursive top-down approach to a problem with the overlapping subproblems property, we can improve things by modifying the procedure to save the result of each subproblem (in an array or hash table). The procedure now first checks to see whether it has previously solved the subproblem. If so, it returns the saved value; if not, it computes, stores, and returns it. It is said that the recursive procedure has been memoized, remembering what results it has computed previously. Such an approach is therefore usually called top-down with memoization. The following code snippet adapts the previous one to use memoization:

public int topDownWithMemoizationAux(int W, int weights[], int values[], int n, int[][] memo) {
  if (n == 0 || W == 0)
    return 0;
  if (memo[n][W] == -1) {
    if (weights[n - 1] > W)
      memo[n][W] = topDownWithMemoizationAux(W, weights, values, 
                   n - 1, memo);
    else
      memo[n][W] = Math.max(
        values[n - 1] + topDownWithMemoizationAux(W - weights[n - 1], 
        weights, values, n - 1, memo),
        topDownWithMemoizationAux(W, weights, values, n - 1, memo));
  }
  return memo[n][W];
}

By applying memoization, we reduce the runtime complexity of the algorithm from exponential (2ⁿ) to quadratic (n*W). It is also possible to solve this problem using a bottom-up approach.

Use of a bottom-up approach typically depends on some natural notion of the size of the subproblems. We must sort the subproblems by size and solve them in order, smallest first, so that we're sure that we already have computed the solutions for smaller subproblems when we need them for a larger one.

A bottom-up approach usually yields the same asymptotic running time as a top-down approach, but it is typical for it to have much better constant factors, since it has less overhead for procedure calls. A bottom-up approach for solving the 0-1 Knapsack problem is shown in the following code snippet:

public int topDownWithMemoizationAux(int W, int weights[], 
  int values[], int n, int[][] memo) {
    if (n == 0 || W == 0)
      return 0;
      if (memo[n][W] == -1) {
        if (weights[n - 1] > W)
          memo[n][W] = topDownWithMemoizationAux(W, weights,
            values, n - 1, memo);
        else
          memo[n][W] = Math.max(
            values[n - 1] +
            topDownWithMemoizationAux(W - weights[n - 1], 
            weights, values, n - 1, memo), 
            topDownWithMemoizationAux(W, weights,
            values, n - 1, memo));
      }
      return memo[n][W];
}