经典动态规划：0-1 背包问题

labuladong原创动态规划背包问题约 1793 字

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

Prerequisites

Before reading this article, you should learn:

Dynamic Programming Core Framework

Tip

本文有视频版：0-1 Knapsack Problem Explained。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

Many people ask about the knapsack problem daily. It's not difficult. With the dynamic programming mindset, 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. Description:

You have a backpack that can hold a weight of W and N items, each with weight and value attributes. The weight of the i-th item is wt[i], and its value is val[i]. Your task is to pack these items in the backpack, with each item used only once. Under the condition that the total weight does not exceed the backpack's capacity, what is the maximum value you can achieve?

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, meaning you choose the first two items, with a total weight of 3, which is less than W, achieving the maximum value of 6.

The problem is straightforward, a typical dynamic programming problem. In this problem, items cannot be split; they must either be fully included or excluded. This is where the term "0-1 knapsack" comes from.

There are no clever methods like sorting to solve this problem; you must enumerate all possibilities. Following the approach from our Dynamic Programming Detailed Explanation, just go through 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.

相关信息

Why define it this way? Because it allows us to find the state transition relationship, or you can consider it a special definition method for knapsack problems. Just remember this approach as a pattern. In the future, when you encounter dynamic programming problems, you can try defining it this way.

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:

java 🟢

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];
}

cpp 🤖

#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];
}

python 🤖

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]

go 🤖

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
}

javascript 🤖

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];
};

注

Actually, the item count N in the function signature is just the length of the wt array, so this parameter N is redundant. However, to reflect the original 0-1 knapsack problem, I've included this parameter N. You can omit it when you write your own code.

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.

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣
1235. Maximum Profit in Job Scheduling	1235. 规划兼职工作