背包问题
给定一组物品,每种物品都有自己的重量和价值,现有一个背包,能承受的重量有限,在受限制的重量下,去取若干物品使总价值最大。
可拆分背包问题
有$N$件物品和一个容积为$V$的背包。每件物品具有体积$c_i$和价值$w_i$。每件物品可以分割成任意大小后放入背包,且单位价值体积不变。该背包中最多可以放入的物品总价值为多少?
我们总是优先挑选单位体积内价值较高的物品放入背包内,所以对于每种物品,先计算其价值对体积的比值(性价比)$r_i=\frac{w_i}{c_i}$,之后对$r_i$进行排序后优先选择性价比较高的物品即可。
可拆分背包问题作为一种较为简单的背包,正是由于其可拆分的性质,所以能够使用贪心轻易地解决。
01背包问题
当前有$N$件物品和一个容积为$V$的背包。已知第i件物品的体积是$c_i$,价值是$w_i$。每种物品有且仅有一件,并且体积不可分割,只能选择放入或者不放入背包。现在需要选出若干件物品,在重量之和不超过V的条件下,使得总价值尽可能大。
算性价比?
反例:
$c_i$ | $w_i $ | 性价比 |
---|---|---|
4 | 8 | 2 |
3 | 5 | $\frac{5}{3}$ |
3 | 4 | $\frac{4}{3}$ |
$V=6$
暴搜?
放或不放 $O(2^n)$
动态规划:
状态:前$i$个物品,总重量不超过$j$的前提下。所获得的最大价值为$dp[i][j]$。
转移方程:
核心代码:
1 | for (int i = 1; i <= N; ++i) { |
优化:转移时第一维只与i-1
和i
有关,因此我们可以将dp数组压缩
1 | int dp[2][V]; |
多重背包问题
有$N$种物品,第$i$种物品的体积是$c_i$,价值是$w_i$,每种物品的数量都是有限的,为$n_i$。现有容量为$V$的背包,请你放入若干物品,在总体积不超过$V$的条件下,使总价值尽可能大。
解法一:
将$N$种物品逐个拆分,得到$\sum{n_i}$个独立物品后用01背包解决。$O(V\sum{n_i})$
解法二:
在转移的过程中枚举第$i$个物品选取的数量$k$,和01背包的思想一样。
复杂度$O(V\sum{n_i})$
核心代码:
1 | for (int i = 1; i <= N; i++) { |
这份代码和01背包相比不再有else
部分了,因为k=0
的时候dp[i][j]=max(dp[i-1][j],dp[i][j])
,相当于01背包的else
部分。
优化:
和01背包一样,由于转移方程只用到i
和i-1
,可以转成滚动数组,但由于dp[i][j]
依赖初始值,所以在每次j
循环开始之前一定要
1 | memset(dp[flag],0,sizeof(dp[flag])); |
完全背包问题
当前有$N$种物品,第$i$种物品的体积是$c_i$,价值是$w_i$。每种物品的数量是无限的,可以任意选择若干件。现有容量为$V$的背包,请你放入若干物品,使总体积不超过$V$,并且总价值尽可能大。
解法:虽然物品个数是无限的,但是实际上,由于背包容量有上限,每个物品最多选取的个数也是有限制的,这样可以转换成多重背包问题$n_i=\frac{V}{c_i}$,进而可以转换成01背包问题。
核心代码:
1 | for (int i = 1; i <= N; i++) { |
时间效率优化:
我们可以注意到
而
也就是说,我们完全可以用dp[i][j-c[i]]
的信息去更新dp[i][j]
,而不用多此一举去枚举k
了,转移可以直接变成如下
1 | for (int i = 1; i <= n; i++) { |
背包问题的空间优化
二维转一维
以01背包为例:
原来的滚动数组代码:
1 | int flag = 1; |
如果我们把 dp
数组只开成一维表示体积,然后从大到小枚举体积,也就是从 $V$到$0$枚举,则当前引用的 dp[j]
和dp[j-c[i]]
仍然是计算第i-1
件物品的结果,即二维状态下的dp[1-flag][j]
, dp[1-flag][j-c[i]]
,因为我们之前没有更新过dp[1-flag][j]
,dp[1-flag][j-c[i]]
的值。
故我们可以简化转移方程:
1 | for (int i = 1; i <= n; i++){ |
同理,多重背包:
1 | for (int i = 1; i <= N; i++) { |
完全背包:
1 | for (int i = 1; i <= n; i++) { |
节省了一半空间。
扩展——分组背包问题
当前有$N$种物品,第$i$种物品的体积是$c_i$,价值是$w_i$。每种物品有且仅有一件。这些东西被分为$K$组,同组的物品不能同时放入背包。现有容量为$V$的背包,请你放入若干物品,使总体积不超过$V$,并且总价值尽可能大。
解法:
在考虑最优解时,对于每一组内的物品有两种选择策略,要么选择组中的某一个物品放入背包,要么包内的任何一个物品都不选入背包。考虑到该策略与 01 背包的相似性,我们可以将一组物品抽象成单独的物品。首先使用朴素的 01 背包写法,用 dp[i][j]
表示枚举到第 $i$ 组物品时,背包体积不超过 $j$ 的最大价值和。
而与 01 背包不同的是,对于组内的每一个物品需要逐一枚举。
核心代码:
1 | for (int i = 1; i <= K; i++) { |
总结
背包类型 | 每种物品数量 | 基本解法 |
---|---|---|
01背包 | 1个 | 动规,双循环选最大值 |
多重背包 | 若干个 | 在01的基础上枚举选择的数量或将物品拆分成独立物品后按01来做 |
完全背包 | 无限 | 算出可放物品最大数量后按多重背包做 |
作业:洛谷