DP - Memory reduction - Competitive Programming

DP - Memory reduction

We will now show how we can reduce the memory from $O(n \cdot C)$ to $O(C)$ of the bottom-up DP solution we developed for the Knapsack.

This technique is not usually necessary in programming contests but it is nice to know it anyway. It also illustrates one advantage of bottom-up DP compared to top-down DP.

If we look at the recurrence:

\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 can observe that the values of states for a given $i$ only depend on the values for $i - 1$. Thus, we don't need to keep the full matrix in memory, we only need to keep the last line.

The straightforward way to implement this is to use a temporary array on which we compute the new values and then update the $dp$ array at the end of each iteration as shown in the code below.

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

However we can actually work directly on a single array $dp$ if we do it in a clever way. The advantage is mostly that we get a very compact code.

The problem of doing straight dp[c] = Math.max(take, skip); is that it will overwrite the value of the state $(i - 1, c)$ with the value of state $(i, c)$ and it could be the case that a later state $(i, c')$ with $c' > c$ also depends on $(i - 1, c)$.

We can overcome this problem by noticing that that $dp(i, c)$ only depends on $dp(i - 1, c')$ for $c' \leq c$. Therefore if we compute the states in decreasing order of $c$ instead of increasing, we will avoid this problem.

static int knapsack(int C, int n, int[] w, int [] v) {
    int[] dp = new int[C + 1];
    for(int i = 0; i < n; i++) {
        for(int c = C; c >= 0; c--) { // loop in decreasing order
            int take = c - w[i] >= 0 ? v[i] + dp[c - w[i]] : Integer.MIN_VALUE;
            int skip = dp[c];
            dp[c] = Math.max(take, skip);
        }
    }
    return dp[C];
}

We can reduce the code further by putting the take conditions directly into the for loop for $c$.

static int knapsack(int n, int C, int[] v, int [] w) {
  int[] dp = new int[C + 1];
  for(int i = 0; i < n; i++) {
    for(int c = C; c >= w[i]; c--) { // stop at w[i] to avoid the if
      dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]);
    }
  }
  return dp[C];
}

WARNING

Condensed code is nice because it takes less time to type and takes less space in your cheatsheets. However, it is often harder to read and makes it more likely that you will forget how it works because it requires you to remember some clever observations. Also, is it less customizable. For example, with the above code you cannot reconstruct the solution.

עליך להדביק את הפקודה הזאת במסוף שלך:

הסיסמה להתחברות אל

Knapsack low memory

Put all the pieces that we discussed above together and write a solution for the Knapsack problem with reduced memory usage.

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$.

Do not forget to print the answer as an int and not a double.

Constraints