Information

Author(s) François Aubry
Deadline Keine Frist
Abgabenlimit No limitation

Einloggen

DP - Top down VS Bottom up

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.

\begin{equation*} dp(0, c) = \begin{cases} v_0 & \quad \text{if $w_0 \leq c$}\\ 0 & \quad \text{otherwise} \end{cases} \end{equation*}

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\).
\begin{equation*} dp(i, c) = \max \begin{cases} v_i + dp(i - 1, c - w_i) & \quad \text{take item $i$}\\ dp(i - 1, c) & \quad \text{skip item $i$} \end{cases} \end{equation*}

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];
}

Knapsack (same problem as before)

Put all the pieces that we discussed above together and write a bottom-up solution for the Knapsack problem (the task will not check whether your solution is a bottom-up solution).

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

A single line with an integer giving the maximum value that can be achieved by taking a subset of the items with total weight at most \(C\).

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.0 MiB
Allowed extensions: .java, .cpp, .py