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.

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.