Classic DP: 0-1 Knapsack Problem

There are frequent inquiries about the knapsack problem. It's not particularly difficult; it mainly involves the state + choice concept of dynamic programming, with nothing extraordinary. Today, let's discuss the knapsack problem, focusing on the most common 0-1 knapsack problem. Description:

You are given a knapsack that can carry a weight of W and N items, each with a weight and a value. The weight of the i-th item is wt[i], and its value is val[i]. You are to pack items into the knapsack, using each item only once, to achieve the maximum value without exceeding the knapsack's capacity.

Here's a simple example with the following input:

N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]

The algorithm returns 6, indicating that by selecting the first two items to pack into the knapsack, the total weight is 3, which is less than W, and the maximum value obtained is 6.

The problem is straightforward, a typical dynamic programming problem. The items in this problem cannot be divided; they must either be packed whole or not at all, which is why it's called the 0-1 knapsack problem.

There is no sophisticated method like sorting to solve this problem; you must enumerate all possibilities. According to our Detailed Explanation of Dynamic Programming, you simply follow the process.

Standard Approach for Dynamic Programming

It seems that the approach needs to be repeated in every dynamic programming article. The dynamic programming problems in previous articles all follow the approach below.

The first step is to clarify two points: 'State' and 'Choice'.

First, let's talk about the state. How can you describe a problem scenario? Just give a few items and a backpack capacity limit, and you have a backpack problem. So, there are two states: 'Backpack Capacity' and 'Available Items'.

Next, the choice is also easy to think about. For each item, what can you choose? The choice is either 'Put in the backpack' or 'Do not put in the backpack'.

Once you understand the state and choice, the dynamic programming problem is almost solved. For a bottom-up thinking approach, the general code framework looks like this:

for state1 in all_values_of_state1:
    for state2 in all_values_of_state2:
        for ...
            dp[state1][state2][...] = best_choice(choice1, choice2...)

The second step is to define the dp array clearly.

First, look at the 'states' we identified earlier. There are two, which means we need a two-dimensional dp array.

The definition of dp[i][w] is as follows: For the first i items, with a current backpack capacity of w, the maximum value that can be packed is dp[i][w].

For example, if dp[3][5] = 6, it means: For a given set of items, if only the first 3 items are considered, when the backpack capacity is 5, the maximum value that can be packed is 6.

Based on this definition, the final answer we want to find is dp[N][W]. The base case is dp[0][..] = dp[..][0] = 0, because if there are no items or the backpack has no space, the maximum value that can be carried is 0.

Refining the above framework:

int[][] dp[N+1][W+1]
dp[0][..] = 0
dp[..][0] = 0

for i in [1..N]:
    for w in [1..W]:
        dp[i][w] = max(
            put item i in the backpack,
            do not put item i in the backpack
        )
return dp[N][W]

Step 3, think about the logic of state transition based on the "choices".

Simply put, how do we code the "put item i in the backpack" and "do not put item i in the backpack" in the pseudocode above?

This requires combining the definition of the dp array to see what impact these two choices have on the state:

Let's restate the definition of our dp array:

dp[i][w] represents: for the first i items (counting from 1), when the current backpack capacity is w, the maximum value that can be accommodated in this scenario is dp[i][w].

If you do not include the i-th item in the backpack, then obviously, the maximum value dp[i][w] should be equal to dp[i-1][w], inheriting the previous result.

If you include the i-th item in the backpack, then dp[i][w] should be equal to val[i-1] + dp[i-1][w - wt[i-1]].

First, since array indices start from 0, and our definition of i starts from 1, val[i-1] and wt[i-1] represent the value and weight of the i-th item.

If you choose to include the i-th item in the backpack, you get the value val[i-1] of the i-th item. Next, you need to select from the first i - 1 items under the remaining capacity w - wt[i-1] to maximize the value, which is dp[i-1][w - wt[i-1]].

In summary, these are the two choices we have analyzed, and we have written the state transition equation. We can further refine the code:

for i in range(1, N + 1):
    for w in range(1, W + 1):
        dp[i][w] = max(
            dp[i-1][w],
            dp[i-1][w - wt[i-1]] + val[i-1]
        )
return dp[N][W]

Finally, translate the pseudocode into actual code and handle some edge cases.

I wrote the code in Java, translating the above logic completely and handling the issue where w - wt[i-1] might be less than 0, causing array index out of bounds:

int knapsack(int W, int N, int[] wt, int[] val) {
    assert N == wt.length;
    // base case has been initialized
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // in this case, we can only choose not to put it in the backpack
                dp[i][w] = dp[i - 1][w];
            } else {
                // choose the better option between putting it in the backpack or not
                dp[i][w] = Math.max(
                    dp[i - 1][w - wt[i-1]] + val[i-1], 
                    dp[i - 1][w]
                );
            }
        }
    }
    
    return dp[N][W];
}

#include <cassert>

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
    assert(N == wt.size());
    // base case is initialized
    vector<vector<int>> dp(N + 1, vector<int>(W + 1));
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // in this case, we can only choose not to put it in the backpack
                dp[i][w] = dp[i - 1][w];
            } else {
                // choose the best option between putting it in the backpack or not
                dp[i][w] = max(
                    dp[i - 1][w - wt[i-1]] + val[i-1], 
                    dp[i - 1][w]
                );
            }
        }
    }

    return dp[N][W];
}

def knapsack(W: int, N: int, wt: List[int], val: List[int]) -> int:
    assert N == len(wt)
    # base case has been initialized
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for w in range(1, W + 1):
            if w - wt[i-1] < 0:
                # in this case, we can only choose not to put it in the backpack
                dp[i][w] = dp[i - 1][w]
            else:
                # choose the best option between putting it in the backpack or not
                dp[i][w] = max(
                    dp[i - 1][w - wt[i-1]] + val[i-1], 
                    dp[i - 1][w]
                )
    return dp[N][W]

func knapsack(W, N int, wt, val []int) int {
    // base case has been initialized
    dp := make([][]int, N+1)
    for i := range dp {
        dp[i] = make([]int, W+1)
    }
    for i := 1; i <= N; i++ {
        for w := 1; w <= W; w++ {
            if w-wt[i-1] < 0 {
                // in this case, we can only choose not to put it in the backpack
                dp[i][w] = dp[i-1][w]
            } else {
                // choose the best option between putting it in the backpack or not
                dp[i][w] = max(
                    dp[i-1][w-wt[i-1]]+val[i-1],
                    dp[i-1][w],
                )
            }
        }
    }

    return dp[N][W]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

var knapsack = function(W, N, wt, val) {
    // base case has been initialized
    var dp = new Array(N + 1).fill().map(() => new Array(W + 1).fill(0));
    for (var i = 1; i <= N; i++) {
        for (var w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // in this case, we can only choose not to put it in the backpack
                dp[i][w] = dp[i - 1][w];
            } else {
                // choose the best option, either put it in the backpack or not
                dp[i][w] = Math.max(
                    dp[i - 1][w - wt[i-1]] + val[i-1], 
                    dp[i - 1][w]
                );
            }
        }
    }

    return dp[N][W];
};

With this, the knapsack problem is solved. In my opinion, this is a relatively simple dynamic programming problem because the derivation of the state transition is quite natural. Basically, once you clearly define the dp array, you can logically determine the state transition.