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

Info

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

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:

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

注

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. 规划兼职工作 |