The solution that we developed for the Knapsack problem where we solve our problem with a recursive function and memoize the results is called top-down dynamic programming.

There is another way to implement a DP algorithm which is called bottom-up. In most cases, the choice of which one you use should be based on the one you are more comfortable writing. Personally I feel that top-down DP is more intuitive but this varies from one person to another.

You should know both ways and be able to switch between them easily as in some cases one is more efficient than the other. We will see examples of this in more advanced DP problems.

For now let's explain what bottom-up DP consists of and write such a solution for the Knapsack problem.

In our previous solution we defined the DP subproblems

In the top-down DP solution we defined the states and subproblems starting from the problem that we want to solve. That is, having all objects available and a knapsack of capacity \(C\).

In bottom-up DP we will write an iterative solution to compute the value of every state. We will start from the smallest subproblems and iteratively increase the size and compute the new solutions from the ones we already know. This means that we will have to redefine the subproblems. Then we will need to find how the solution of the problem changes when a new object becomes available.

We define the subproblems as follows:

\(dp(i, c)\) is the maximum value we can obtain by selecting a subset of the objects \(0, 1 \ldots, i\) from a knapsack of capacity \(c\).

Notice that now when we increase \(i\) we are considering more objects whereas in the previous definition it would consider less objects.

The easy subproblems correspond to states where \(i = 0\), that is, we only have one object. In this case, we either get value \(v_0\) if object fits the knapsack or 0 otherwise.

Now we need to express the solution of \(dp(i, c)\) with the values of smaller subproblems. In this case, subproblems \((i', c')\) where \(i' \leq i\) and \(c' \leq c\).

The recurrence relation will naturally be very similar to the previous one. Again, we have two choices: either we take object \(i\) or we skip it.

• If we take it then we will take the remaining items \(0, 1, \ldots, i - 1\) in the best way possible but in a knapsack of capacity \(c - w_i\).
• If we don't take it then we will take the remaining items in the best way possible in a knapsack of capacity \(c\).

We need to be careful with the fact that we can only take item \(i\) if it fits the knapsack. Otherwise \(c - w_i < 0\) and \(dp(i - 1, c - w_i)\) is undefined. We can treat these cases to have value \(-\infty\) so they are ignored in the maximization.

In bottom-up DP we usually compute the values by creating a matrix that has one entry per subproblem and then iterate over the states in order and use the recurrence relation to compute the values. The following code gives a possible implementation.

static int knapsack(int n, int C, int[] v, int [] w) {
  int[][] dp = new int[n][C + 1];
  // initialize the base cases
  for(int c = 0; c <= C; c++) {
    dp[0][c] = c - w[0] >= 0 ? v[0] : 0;
  }
  // loop and apply recurrence
  for(int i = 1; i < n; i++) {
    for(int c = 0; c <= C; c++) {
      int take = c - w[i] >= 0 ? v[i] + dp[i - 1][c - w[i]] : Integer.MIN_VALUE;
      int skip = dp[i - 1][c];
      dp[i][c] = Math.max(take, skip);
    }
  }
  return dp[n - 1][C];
}