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.

Dynamic Programming Standard Approach

It seems every dynamic programming article needs to reiterate the approach, as all historical articles on dynamic programming problems follow the approach outlined below.

The first step is to clarify two things: "state" and "choice".

First, let's talk about the state. How can we describe the situation of a problem? If you are given several items and a capacity limit for a backpack, it forms a knapsack problem. So there are two states: "capacity of the backpack" and "available items to choose from".

Now, let's discuss choice. It's quite straightforward, really. What choices can you make for each item? The choices are "put it in the backpack" or "don't put it in the backpack".

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

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

The second step is to clarify the definition of the dp array.

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

Why define it this way? Because it helps identify the state transition relationship, or it's a specific way to define a knapsack problem. Just remember it as a pattern. In future scenarios similar to the knapsack problem, you can try defining it this way.

According to this definition, the final answer we want to find is dp[N][W]. The base case is dp[0][..] = dp[..][0] = 0, because when there are no items or the knapsack has no capacity, the maximum value that can be packed 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(
            packing item i into the knapsack,
            not packing item i into the knapsack
        )
return dp[N][W]

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

Simply put, how are the choices "packing item i into the knapsack" and "not packing item i into the knapsack" expressed in code?

This requires combining the definition of the dp array to see how these two choices affect the state:

Restating our dp array definition:

dp[i][w] represents: for the first i items (starting count from 1), when the current capacity of the knapsack is w, the maximum value that can be packed in this situation is dp[i][w].

If you do not pack the i-th item into the knapsack, then clearly, the maximum value dp[i][w] should equal dp[i-1][w], inheriting the previous result.

If you pack the i-th item into the knapsack, then dp[i][w] should equal val[i-1] + dp[i-1][w - wt[i-1]].

Firstly, since array indices start from 0, and in our definition 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 pack the i-th item into the knapsack, then the value val[i-1] of the i-th item is certainly acquired. Next, you need to select from the first i - 1 items under the remaining capacity w - wt[i-1] to find the maximum value, i.e., dp[i-1][w - wt[i-1]].

In summary, these are the two choices we have analyzed, which means we have written the state transition equation and can further refine 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]

The final step is to translate the pseudocode into code and handle some edge cases.

I have translated the above idea completely into Java code and handled the issue where w - wt[i-1] might be less than 0, leading to an 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 resolved. In my opinion, this is a relatively straightforward dynamic programming problem, as the derivation of the state transition is quite natural. Once you clearly define the dp array, determining the state transition follows logically.