Classic DP: 0-1 Knapsack Problem

Many people frequently ask about the knapsack problem. Actually, it's not difficult. Using the dynamic programming approach, it's just about states and choices—nothing special. Today, let's discuss the knapsack problem, focusing on the most common 0-1 knapsack problem. Problem description:

You have a knapsack with a capacity of W, and N items. Each item has a weight and a value. The weight of the ith item is wt[i], and its value is val[i]. You can put items into the knapsack, but each item can only be used once. What is the maximum total value you can carry in the knapsack without exceeding its capacity?

Here's a simple example. Input:

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

The algorithm returns 6. You can put the first two items into the knapsack, with a total weight of 3, which is less than W, and the maximum value you can get is 6.

That's the whole problem—a classic dynamic programming problem. The items cannot be divided; you either put an item in the knapsack or you don't. You can't split an item. This is where the name 0-1 knapsack comes from.

There is no clever sorting or shortcut to solve this problem. You have to try all possible combinations. Following the pattern from our Dynamic Programming Detailed Explanation, just follow the process step by step.

Standard Dynamic Programming Template

It seems like every dynamic programming article needs to repeat this template. All the past dynamic programming problems use the same steps.

Step 1: Make clear two things: "state" and "choice".

Let's talk about state first. How can you describe the situation of a problem? As long as you have some items and a backpack with a capacity limit, you have a knapsack problem. So, the two states are "backpack capacity" and "items you can choose".

Now, what about choice? It's easy to think of. For each item, what can you do? You can "put it into the backpack" or "not put it into the backpack".

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

for state1 in all possible values of state1:
    for state2 in all possible values of state2:
        for ...
            dp[state1][state2][...] = best_of(choice1, choice2, ...)

Step 2: Make clear the definition of the dp array.

Look at the "states" we just found. There are two. That means we need a 2D dp array.

Why define it like this? Because it helps you find the state transition. You can remember this as a template. In the future, for similar knapsack problems, you can define it the same way.

Based on this definition, the final answer we want is dp[N][W]. The base cases are dp[0][..] = 0 and dp[..][0] = 0, because if there are no items or the backpack has no space, the maximum value you can carry is 0.

Let’s make the structure more detailed:

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 the i-th item into the backpack,
            do not put the i-th item into the backpack
        )
return dp[N][W]

Step 3: According to the "choices", think about the state transition logic.

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

This depends on our definition of the dp array, and how the two choices affect the state.

Let’s say it again:

dp[i][w] means: for the first i items (counted from 1), with current backpack capacity w, the maximum value you can carry is dp[i][w].

If you do not put the i-th item into the backpack, then obviously, the maximum value dp[i][w] should be the same as dp[i-1][w], inheriting the previous result.

If you put the i-th item into the backpack, then dp[i][w] should be val[i-1] + dp[i-1][w - wt[i-1]].

Here, since array indexes start from 0, but our definition of i starts from 1, so val[i-1] and wt[i-1] mean the value and weight of the i-th item.

If you choose to put the i-th item into the backpack, you get its value val[i-1]. Next, with the remaining capacity w - wt[i-1], you choose from the first i-1 items, and get the maximum value dp[i-1][w - wt[i-1]].

These are the two choices. Now we can write the state transition equation and further improve the code:

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

Final step: Translate the pseudocode into real code and handle edge cases.

Here is the Java code version. It follows the above logic and also handles the case where w - wt[i-1] might be less than 0, which could cause an array index error:

int knapsack(int W, int[] wt, int[] val) {
    int 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, vector<int>& wt, vector<int>& val) {
    int 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, wt: List[int], val: List[int]) -> int:
    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 int, wt, val []int) int {
    N := len(wt)
    // 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, wt, val) {
    let N = wt.length;
    // base case has been initialized
    let dp = new Array(N + 1).fill().map(() => new Array(W + 1).fill(0));
    for (let i = 1; i <= N; i++) {
        for (let 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];
};

That's it. The knapsack problem is solved. In my opinion, this is a relatively simple dynamic programming problem, because the state transition is natural. Once you understand the definition of the dp array, you can easily write out the state transitions.