背包问题概述
背包问题(Knapsack Problem)是计算机科学和运筹学中的一个经典问题,通常描述为:给定一组物品,每种物品都有自己的重量和价值,在限定的最大承重(背包容量)下,如何选择物品使得背包内物品的总价值最大。
背包问题有多种表现形式,包括但不限于:
- 0/1背包问题:有 n 种物品,每种物品只能选一次,即不能拆分。这是最基本的背包问题。
- 完全背包问题:有 n 种物品,每种物品可以被选择多次,即可以拆分。
- 多重背包问题:有 n 种物品,每种物品有一个固定的数量限制,即可以选多次,但有上限。
- 二维背包问题:除了重量和价值外,物品和背包还有其他限制条件,如体积等。
背包问题其实还有很多分类,但是我们仅需了解即可。在本篇文章主要讲解其中的0/1背包问题和完全背包问题。
0/1背包问题
问题描述
假设共有a,b,c共3种物品,它们的重量分别是1,3,4,它们的价值分别是15,20,30,现在给你个承重为4的背包, 怎么装背包,背包里物品价值总和最大。
解题思路
一共有两种解法分别是二维dp数组和一维dp数组,一维dp数组是对二维dp数组的优化。我们先来学习二维dp数组。
二维dp数组
回顾一下求解动态规划的一般步骤。
(1)分析题目,定义 dp 数组并且确定 dp[i] 的含义。
(2)找到递推公式
(3)dp 数组初始化
(4)确定遍历顺序
更详细内容详见【初窥算法】初识动态规划(Dynamic programming)
Step1:定义dp数组
dp[i][j] 表示前 i 件物品任取一个放入容量为 j 的背包中所能获得的最大价值。
Step2:找到递推公式
要想找到递推公式,我们就需要知道 dp[i][j] 可以从哪几个状态得到。当前背包的状态,取决于放不放当前这个物品 i 。
- 不放物品 i:不放物品 i 的状态为 dp[i-1][j](即背包容量为j,背包里不放物品i的最大价值),此时 dp[i][j] 就是 dp[i - 1][j] 。此情况其实就是当物品 i 的重量大于背包 j 的重量时,物品 i 无法放进背包中,所以被背包内的价值和前面相同。
- 放物品 i:放物品 i 的前一个状态为 dp[i - 1][j - weight[i]] (背包容量j减去物品i的重量,背包里不放物品i的最大价值),此时 dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值。
此时就有了两个值,我们取最大即为 dp[i][j] 的最大价值。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
Step3:初始化dp数组
以上方题目为例,dp数组的形状为一个二维表格(纵列代表i,横行代表j)。
0 | 1 | 2 | 3 | 4 | |
物品a(0) | |||||
物品b(1) | |||||
物品c(2) |
假如我们要求dp[2][2],我们就需要知道 dp[1][2] 还有 dp[1][?] 的值(?根据物品 i 的重量确定)。因此我们需要初始化 dp 数组的第一列和第一行。
- 第一列:
dp[i][0] = 0
,表示背包容量为 0 时无法放入任何物品,价值为0。 - 第一行:此时分为两种情况,由物品 0 的重量决定。
- 当背包容量小于物品 0 的重量(weight[0])时:dp[0][j] = 0
- 当背包容量大于等于物品 0 的重量(weight[0])时,dp[0][j] = value[0]
针对上方问题,初始化 dp 数组结果为:
0 | 1 | 2 | 3 | 4 | |
物品a(0) | 0 | 15 | 15 | 15 | 15 |
物品b(1) | 0 | ||||
物品c(2) | 0 |
Step4:确定遍历顺序
先遍历物品(i)还是先遍历背包(j)都是可以的,且第二层for循环是从小到大遍历。
一维dp数组
一维dp数组是在二维dp数组进行空间上的优化。
在使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
其实可以发现如果把 dp[i - 1] 那一层拷贝到 dp[i] 上,表达式完全可以是:dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])。与其把dp[i - 1]这一层拷贝到dp[i]上,不如只用一个一维数组了,只用dp[j](一维数组,也可以理解是一个滚动数组)。
Step1:定义dp数组
在一维dp数组中,dp[j]表示:容量为 j 的背包,所背的物品价值可以最大为 dp[j] 。
Step2:找到递推公式
此时dp[j]有两个选择:
- 不放物品i:取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]。
- 放物品i:取dp[j - weight[i]] + value[i],指定是取最大的。
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
Step3:初始化dp数组
dp[0]表示背包容量为0所背的物品的最大价值,因此应该初始化为0。其他的也初始化为0,这样在递归的时候,才会被覆盖成较大的值。
Step4:确定遍历顺序
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}
在遍历背包容量时选择从大到小遍历,是为了保证物品i只被放入一次!但如果一旦从小到大遍历了,那么物品0就会被重复加入多次!