01背包问题及其优化
01背包问题及其优化
【算法标签】 动态规划、背包问题(01/多重/完全)
【语法标签】 :数组、for循环、max、二维数组、滚动数组、一维优化
当前有 件物品和一个容积为 的背包。已知第 件物品的体积是 ,价值是 。每种物品 有且仅有一件,并且 体积不可分割,因此只能选择放或不放。现在需要选出若干件物品,在它们的体积之和不超过 的条件下,使得价值总和尽可能大。
我们将这类问题称之为 01 背包问题。
对于每个物品是否要装入背包,我们自然可以进行暴力枚举或搜索,但是如果要暴力地去做,那么时间复杂度会非常的高(指数级);
这时候需要一种更优的算法——动态规划。
对于 01 背包,先确定这个问题的状态。
- 共有 N 个物品,背包总容量为 V,那么可以根据物品和容量来确定一个状态。
- 前 i 个物品,放在背包里,体积之和不超过 的前提下,所获得的最大价值为 。
是否将第 i 个物品装入背包中,就是决策。
- 当容量小于第 i 个物品的体积时,我们无法将其放入背包。
- 为了使价值最大化,如果第 i 个物品放入背包后,总体积不超过限制且总价值比之前要大,那么就将第 i 个物品放入背包。
根据这个逻辑写出转移方程:
当 时,
当 时,
为了更好地理解这个转移方程,看一个具体的例子:
有 5 个物品,编号 1-5,体积分别是 [2,2,6,5,4],价值分别是 [6,3,5,4,6],背包的总容积为 10。列出本问题中所有的状态变量,也就是转移方程中的 dp 变量,且初始化为 0。 当第一个物品放入背包,因为第一个物品体积为 2 ,价值为 6,只要背包容量大于等于 2,都可以放第一个物品。
根据我们的转移方程 ,那么:

根据我们的转移方程继续放第二个物品,容量为2,3 的时候:,则 。 容量大于 3 的时候: ,则 。dp 变量表被更新为:

当放第 3 个物品的时候,第三个物品的体积 ,所以
在背包容量 的时候,。
在背包容量 的时候, 。dp 变量表被更新为: 
当放第 3 个物品的时候,第三个物品的体积 ,所以
在背包容量 的时候,。
在背包容量 的时候, 。
dp 变量表被更新为: 
核心代码
时间上是两重循环,时间复杂度为
空间是二维的,空间复杂度也为
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= V; ++j) {
if(j >= c[i]) {
dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}二、01背包问题的空间优化:滚动数组
回顾一下 01 背包的计算过程,当我们计算这个表格中第 行的结果时,只会用到第 行的结果,而前面的 行数据都不会被用到。能不能借助这个性质,降低 01 背包的空间复杂度呢?

我们把编号按照奇偶性分组,其中偶数的标记为圆圈,奇数的标记为方块。实际上,我们只需要保存相邻两行的结果,那么就可以把原来的二维数组压缩成第一维大小为 2:
int dp[2][V];其中,保存偶数行的结果,而则保存奇数行的结果。

这样,我们在逐行计算原来 结果的时候,如果 是奇数,对应的状态转移方程就是
dp[1][j] = max(dp[0][j], dp[0][j - c[i]] + w[i])而当 是偶数的时候,对应的状态转移方程就是
dp[0][j] = max(dp[1][j], dp[1][j - c[i]] + w[i])这样当我们算到第 行的时候,最终的结果就是 ][V],其中 当 为奇数时为 ,否则为 ;在实现代码的时候,我们可以用一个变量 来表示当前行的奇偶,那么 就是前一行的奇偶。 表示总体积。
进行状态压缩后的 01 背包代码见右:
空间复杂度压缩至 时间复杂度仍然是
flag = 1; // 初始时 flag 为 1
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= V; ++j) {
if(j >= c[i]) {
dp[flag][j] = max(dp[1 - flag][j - c[i]] + w[i], dp[1 - flag][j]);
} else {
dp[flag][j] = dp[1 - flag][j];
}
}
flag = 1 - flag; // 当前行结束,flag 进入下一行之前修改
}或者,使用 的结果作为
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= V; ++j) {
if(j >= c[i]) {
dp[i % 2][j] = max(dp[ (i - 1) % 2 ][j - c[i]] + w[i], dp[ (i - 1) % 2 ][j]);
} else {
dp[i % 2][j] = dp[ (i - 1) % 2 ][j];
}
}
}三、01背包问题的空间优化:一维数组优化
在前面的讲解中我们可以意识到,整个动态规划的过程,状态都是 从上到下、从左往右 转移的。 
观察图片我们也可以发现这个规律。
- 对于第 个物品, 当 时,第 个物品并不能被选择, 直接从上一层的状态 转移而来。
- 当 时,可以选择第 个物品, 此时 直接从上一层的状态 以及 转移而来。
从上一层到下一层的转移过程中,二维数组的第二维 只会受到同样大小的 或者更小的 位置的影响,而不会受到比 大(在 右边)的位置的影响。
此时,用一维数组 从后往前更新 就能实现空间优化了。
- 对于还未更新的部分, 中存储的是上一层的内容。
- 对于已经更新的部分, 中更新为当前层的内容。
- 用还未更新的部分用来更新当前层,可以保证答案的正确性。
具体我们可以来看看代码的实现。
关键代码
for (int i = 1; i <= N; i++) {
for (int j = V; j >= c[i]; j--) { // 循环从背包容积 V 开始,到 c[i] 结束,从大到小枚举
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
// 对于 j 来说,更小的位置 j - c[i] 还未更新,里面存储的是上一层的值,因此可以进行计算
}
}从上面的代码我们可以发现,对于 的部分代码直接不进行处理了。
这是因为,当 时,第 个物品并不能被选择, 值直接沿用上一层(在二维的动态规划中是 。
而一维时,未进行更新的位置 本身就是上一层的值,所以不需要进行额外的操作。
空间复杂度压缩至 ,时间复杂度仍然是 。
多重背包
有 N 种物品,第 i 种物品的体积是 ,价值是 。 与 01 背包不同的是,多重背包每种物品都有若干个,数量为 ,是有限的。 现有容量为 V 的背包,请你放入若干物品,在总体积不超过 V 的条件下,使总价值尽可能大。
算法设计
我们可以把每个种类的 个物品,都当成 01 背包里的不同种物品,只是恰巧体积和价值相同。这样把 个物品逐个拆分,则一共有 个物品。
原问题便转化为一个普通的 01 背包,时间复杂度是 。我们也可以在转移的过程中枚举 ,代表第 个物品选取的数量,和 01 背包的思想一样,有如下转移。
这样的时间复杂度也是 。实际上 01 背包是特殊的多重背包。
这一份代码和 01 背包相比,不再有 else 部分了,因为, 的时候 ,相当于 01 背包的 else 部分。
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
for (int k = 0; k <= n[i]; k++) {
if (j >= c[i] * k) {
dp[i][j] = max(dp[i - 1][j - c[i] * k] + w[i] * k, dp[i][j]);
}
}
}
}既然多重背包的可以转换成 01 背包,那么我们必然也可以像 01 背包那样使用 滚动数组 优化空间复杂度。
完全背包问题
当前有 N 种物品,第 i 种物品的体积是 ,价值是 。每种物品的数量都是无限的,可以选择任意数量放入背包。现有容量为 V 的背包,请你放入若干物品,使总体积不超过 ,并且总价值尽可能大。
虽然物品个数是无限的,但是实际上,由于背包容量有上限,每个物品最多选取的个数也是有限制的,这样可以转换成多重背包问题,进而可以转换成 01 背包问题。
可以用多重背包的思想来解决完全背包。
时间优化
我们可以注意到
而
也就是说,我们完全可以用 的信息去更新 ,而不用去多此一举去枚举 了,转移可以直接变成如下
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= v; j++) {
if (j >= c[i]) {
dp[i][j] = max(dp[i][j - c[i]] + w[i], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}这样我们算法的时间复杂度 ,空间复杂度 。
