经典动态规划:0-1 背包问题
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准,解决了之前 chatGPT 翻译可能出错的问题~
Tip
本文有视频版:0-1背包问题详解。建议关注我的 B 站账号,我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
后台天天有人问背包问题,这个问题其实不难,借助动态规划的思维框架,无非还是状态 + 选择,没啥特别之处。今天就来说一下背包问题吧,就讨论最常见的 0-1 背包问题。描述:
给你一个可装载重量为 W
的背包和 N
个物品,每个物品有重量和价值两个属性。其中第 i
个物品的重量为 wt[i]
,价值为 val[i]
。现在让你用这个背包装物品,每个物品只能用一次,在不超过被包容量的前提下,最多能装的价值是多少?
![](/algo/images/knapsack/1.png)
举个简单的例子,输入如下:
N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]
算法返回 6,选择前两件物品装进背包,总重量 3 小于 W
,可以获得最大价值 6。
题目就是这么简单,一个典型的动态规划问题。这个题目中的物品不可以分割,要么装进包里,要么不装,不能说切成两块装一半。这就是 0-1 背包这个名词的来历。
解决这个问题没有什么排序之类巧妙的方法,只能穷举所有可能,根据我们 动态规划详解 中的套路,直接走流程就行了。
动规标准套路
看来每篇动态规划文章都得重复一遍套路,历史文章中的动态规划问题都是按照下面的套路来的。
第一步要明确两点,「状态」和「选择」。
先说状态,如何才能描述一个问题局面?只要给几个物品和一个背包的容量限制,就形成了一个背包问题呀。所以状态有两个,就是「背包的容量」和「可选择的物品」。
再说选择,也很容易想到啊,对于每件物品,你能选择什么?选择就是「装进背包」或者「不装进背包」嘛。
明白了状态和选择,动态规划问题基本上就解决了,对于自底向上的思考方式,代码的一般框架是这样:
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 择优(选择1,选择2...)
第二步要明确 dp
数组的定义。
首先看看刚才找到的「状态」,有两个,也就是说我们需要一个二维 dp
数组。
dp[i][w]
的定义如下:对于前 i
个物品,当前背包的容量为 w
,这种情况下可以装的最大价值是 dp[i][w]
。
比如说,如果 dp[3][5] = 6
,其含义为:对于给定的一系列物品中,若只对前 3 个物品进行选择,当背包容量为 5 时,最多可以装下的价值为 6。
相关信息
为什么要这么定义?因为这样可以找到状态转移关系,或者说这就是背包问题的特殊定义方式,你当做套路记下来就行,未来遇到动态规划相关问题,都可以这样定义试一试。
根据这个定义,我们想求的最终答案就是 dp[N][W]
。base case 就是 dp[0][..] = dp[..][0] = 0
,因为没有物品或者背包没有空间的时候,能装的最大价值就是 0。
细化上面的框架:
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(
把物品 i 装进背包,
不把物品 i 装进背包
)
return dp[N][W]
第三步,根据「选择」,思考状态转移的逻辑。
简单说就是,上面伪码中「把物品 i
装进背包」和「不把物品 i
装进背包」怎么用代码体现出来呢?
这就要结合对 dp
数组的定义,看看这两种选择会对状态产生什么影响:
先重申一下刚才我们的 dp
数组的定义:
dp[i][w]
表示:对于前 i
个物品(从 1 开始计数),当前背包的容量为 w
时,这种情况下可以装下的最大价值是 dp[i][w]
。
如果你没有把这第 i
个物品装入背包,那么很显然,最大价值 dp[i][w]
应该等于 dp[i-1][w]
,继承之前的结果。
如果你把这第 i
个物品装入了背包,那么 dp[i][w]
应该等于 val[i-1] + dp[i-1][w - wt[i-1]]
。
首先,由于数组索引从 0 开始,而我们定义中的 i
是从 1 开始计数的,所以 val[i-1]
和 wt[i-1]
表示第 i
个物品的价值和重量。
你如果选择将第 i
个物品装进背包,那么第 i
个物品的价值 val[i-1]
肯定就到手了,接下来你就要在剩余容量 w - wt[i-1]
的限制下,在前 i - 1
个物品中挑选,求最大价值,即 dp[i-1][w - wt[i-1]]
。
综上就是两种选择,我们都已经分析完毕,也就是写出来了状态转移方程,可以进一步细化代码:
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]
最后一步,把伪码翻译成代码,处理一些边界情况。
我用 Java 写的代码,把上面的思路完全翻译了一遍,并且处理了 w - wt[i-1]
可能小于 0 导致数组索引越界的问题:
int knapsack(int W, int N, int[] wt, int[] val) {
assert N == wt.length;
// base case 已初始化
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) {
// 这种情况下只能选择不装入背包
dp[i][w] = dp[i - 1][w];
} else {
// 装入或者不装入背包,择优
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 已初始化
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) {
// 这种情况下只能选择不装入背包
dp[i][w] = dp[i - 1][w];
} else {
// 装入或者不装入背包,择优
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 已初始化
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:
# 这种情况下只能选择不装入背包
dp[i][w] = dp[i - 1][w]
else:
# 装入或者不装入背包,择优
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 已初始化
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 {
// 这种情况下只能选择不装入背包
dp[i][w] = dp[i-1][w]
} else {
// 装入或者不装入背包,择优
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 已初始化
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) {
// 这种情况下只能选择不装入背包
dp[i][w] = dp[i - 1][w];
} else {
// 装入或者不装入背包,择优
dp[i][w] = Math.max(
dp[i - 1][w - wt[i-1]] + val[i-1],
dp[i - 1][w]
);
}
}
}
return dp[N][W];
};
注
其实函数签名中的物品数量 N
就是 wt
数组的长度,所以实际上这个参数 N
是多此一举的。但为了体现原汁原味的 0-1 背包问题,我就带上这个参数 N
了,你自己写的话可以省略。
至此,背包问题就解决了,相比而言,我觉得这是比较简单的动态规划问题,因为状态转移的推导比较自然,基本上你明确了 dp
数组的定义,就可以理所当然地确定状态转移了。
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路:
LeetCode | 力扣 |
---|---|
1235. Maximum Profit in Job Scheduling | 1235. 规划兼职工作 |
《labuladong 的算法笔记》已经出版,关注公众号查看详情;后台回复「全家桶」可下载配套 PDF 和刷题全家桶:
![](/algo/images/souyisou2.png)