Classic DP: 0-1 Knapsack Problem
Prerequisite Knowledge
Before reading this article, you should first study:
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.
Definition of dp
array for the knapsack problem
The definition of dp[i][w]
is: for the first i
items, with current backpack capacity w
, the maximum value you can carry is dp[i][w]
.
For example, if dp[3][5] = 6
, it means: among a given set of items, if you only choose from the first 3 items, when the backpack capacity is 5, the most value you can carry is 6.
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];
};
Algorithm Visualization
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.
Related Problems
You can install my Chrome extension then open the link.
LeetCode | Difficulty |
---|---|
1235. Maximum Profit in Job Scheduling | 🔴 |
1262. Greatest Sum Divisible by Three | 🟠 |
3180. Maximum Total Reward Using Operations I | 🟠 |
474. Ones and Zeroes | 🟠 |