当前位置：首页 > news >正文

背包DP（基础篇） - L

news 2025/9/10 6:11:12

L-Coding于2025.7.29作。

一、引言

考虑如下的问题：

有一个容量为V的背包以及n个物体。不考虑物体几何形状，只要背包的剩余容量大于等于物体体积，那这个物体就可以装进背包里。每个物体只能选一次，且每个物体都有两个属性：体积w和价值v。问：如何向背包装物体才能使背包中物体的总价值最大？

由于这是一个求最大值的问题，所以我们可能会考虑到使用贪心算法。

现给出一组数据：背包容量为10，有4个物体，其中它们的体积和价值分别为

`i`	`w`	`v`
1	8	9
2	3	3
3	4	4
4	3	3

若使用贪心，则每一次装入的物品必须是最优方案，每一次都装入单位体积价值最大的物体，即价值与体积比值最大的物体。现计算比值：

`i`	`v*1.0/w`
1	1.125
2	1
3	1
4	1

因此优先装入第一个物体。但发现第一个物体的体积为8，总体积为10，剩余体积则为2，装不下其他物体。综上，使用贪心算法计算得最大价值为9。

不过，我们注意到：如果取物体2、3、4装入背包，所得的最大价值为3+4+3=10，大于贪心算法所得的9。因此，举例而言，这类问题不能用贪心算法处理。至于背包问题究竟为什么不能用贪心算法处理，此处按下不表。

接下来，我们将介绍这类问题的普遍解法：动态规划（DP）。

二、0-1背包

1. 问题分析

再次考虑引言中的问题：背包容量一定，物体种数已知，每个物体只能装一次，且物体价值和体积已知，求背包所能装下物体的最大总价值。

我们知道，对于每个物体而言，只有「被装入背包」和「不被装入背包」两种可能。将这两种可能分别对应二进制中的0和1两种状态，这类问题就被称作0-1背包问题。

既然贪心不行，不妨考虑使用动态规划求解。在0-1背包问题中，可能影响状态的变量有两个：所选的物体种数，以及所选的物体体积。因此，在给状态下定义时，将这两个对状态有影响的变量全部融入进去。

2. 状态定义与答案

定义：dp[i][j]表示选择前i个物品时，容量为j的背包所能装下的最大总价值。容易看出，所求结果即为dp[n][V]。

3. 状态转移

因为要求解背包容量为V时的最大总价值，所以不同的背包容量时的状态一定存在某种转移关系。

假若前i-1个物品的所有状态已经处理好，那么第i个物品就只有两种状态可选：

当不选其放入背包时，背包容量不变，物品总价值也不变，故这种状态下的最大价值继承自dp[i-1][j]不变；
当选其放入背包时，背包剩余容量则会相应地减小所选的第i个物品的体积w[i]，物品总价值也会相应地增加该物品的价值v[i]，故这种状态下的最大价值为dp[i-1][j-w[i]]+v[i]。

综上所述，状态转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])，其中i从1到n遍历，j从0到V遍历。

根据引言中的样例，本题dp数组的转移过程如表所示。

`w[i]`	`v[i]`	`i`/`j`	3	4	5	6	7	8	9	10
8	9	1	0	0	0	0	0	9	9	9
3	3	2	3	3	3	3	3	9	9	9
4	4	3	3	4	4	4	7	9	9	9
3	3	4	3	4	4	6	7	9	9	10

为方便理解，下面举例分析计算dp[4][10]（题目所求）时的步骤。

考虑dp[4][10]的含义：选择前4个物品时，背包容量为10时的最大总价值；
考虑dp[4][10]从何处转移而来：
- 对于第4个物品，若不选其加入背包，则状态相当于选择前3个物品时，背包容量为10不变时的最大总价值，即从dp[3][10]（记作①式）继承而来；
- 若选其加入背包，则背包容量会减去w[4]，总价值会加上v[4]，即从dp[3][10-w[4]]+v[4]（记作②式）转移而来。
计算两式的值并加以比较，发现②式值为10，较大，故dp[4][10]的值为10。

综上所述，可以写出代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int V,n,w[N],v[N],dp[N][N];
int main(){cin>>V>>n;//n个物品for(int i=1;i<=n;i++){cin>>w[i]>>v[i];//分别输入物品的体积和对应的价值}for(int i=1;i<=n;i++){//遍历物品//防止数组下表出现负数，分情况讨论。for(int j=0;j<w[i];j++){dp[i][j]=dp[i-1][j];}for(int j=w[i];j<=V;j++){dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}}cout<<dp[n][V]<<endl;return 0;
}

4. 优化

(1) 状态来源与滚动数组优化

由上表可以看出，每一行的数组值只和上一行有关，所以不难想到将数组删掉一维，仅用一个一维数组动态更新最优方案值。这种优化方案被称为滚动数组优化，它能够起到节省空间的作用，避免MLE，也能扩大数据范围。

(2) 问题

如果强行将第一维删掉，则代码会变为：

for(int i=1;i<=n;i++){for(int j=w[i];j<=V;j++){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}
}

我们现在不妨使用这个规则来根据样例数据填表。

（表1）第一次大循环，i=1：

`j`	0	1	2	3	4	5	6	7	8	9	10
`dp[j]`	0	0	0	0	0	0	0	0	9	9	9

（表2）第二次大循环：i=2：

`j`	0	1	2	3	4	5	6	7	8	9	10
`dp[j]`	0	0	0	3	3	3	6

填到dp[6]时，发现dp[6]数据错误，为什么呢？俯瞰一下：在填入dp[6]时，是将dp[6]自身与dp[6-w[2]]+v[2]比大小，选择较大的值填入。

而在dp[6]的值未被更新时，根据表1，dp[6]为0。可是dp[6-w[2]]即dp[3]的值已经被填好了，还要再加上一个v[2]，这就相当于2号物品被使用了两次。回顾0-1背包问题的性质：每个物品仅能使用一次。

这种优化方式难道就是违背题设的吗？并不是，而是我们的算法优化出现了问题。

让我们将思绪回到刚才出现问题的优化方案中来。

为便于理解，重新使用二维数组dp[i][j]定义状态。广泛而言，当处理前i个物品时，对于状态dp[i][j]，如果j>=w[i]，那么dp[i][j]的值会随着dp[i][j-w[i]]的值的提前确定而发生变化。

对于同一物品而言，这种根据提前确定的状态值来确定未确定的状态值的操作，等价于同一物品被多次放入背包，不符合0-1背包的性质。

(3) 解决方案

注意到，如果逆转j循环遍历的顺序，那么dp[i][j]总会在dp[i][j-w[i]]前被更新，就不会出现上述问题。

5. 模板代码

由此，可得0-1背包的模板代码为：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int V,n,w[N],v[N],dp[N];
int main(){cin>>V>>n;//n个物品for(int i=1;i<=n;i++){cin>>w[i]>>v[i];//输入}for(int i=1;i<=n;i++){//遍历物品for(int j=V;j>=w[i];j--){//逆向遍历背包容量dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[V]<<endl;return 0;
}

三、完全背包

1. 问题导入与分析

完全背包问题与0-1背包问题基本相同，区别仅仅是每个物品可以选取多次。

类比于0-1背包问题，完全背包问题同样适用于动态规划求解。

2. 状态定义与答案

同样地，定义：dp[i][j]表示选择前i个物品时，容量为j的背包所能装下的最大总价值，所求结果即为dp[n][V]。

3. 状态转移

值得注意的是，完全背包问题的状态转移方程与0-1背包并不相同。

我们可以枚举所选物品的个数来进行状态转移。则状态转移方程为dp[i][j]=max(dp[i-1][j-k*w[i]]+k*v[i])，其中i从1到n遍历，j从0到V遍历，k从0到INT_MAX遍历。

这种算法的时间复杂度极高，为O(n^3)，所以考虑优化方案。

4. 优化

由上知，状态dp[i][j]由前继的多个dp[i][j-k*w[i]](k>0)转移而来。

因此，我们不妨正向遍历j，使得状态dp[i][j-w[i]]是考虑之前所有dp[i][j-k*w[i]](k>1)的状态后所决定出的最优方案。

可以使用滚动数组删掉第一维，仅保留第二维，由此得到最终的代码。

5. 模板代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int V,n,w[N],v[N],dp[N];
int main(){cin>>V>>n;//n个物品for(int i=1;i<=n;i++){cin>>w[i]>>v[i];//输入}for(int i=1;i<=n;i++){//遍历物品for(int j=w[i];j<=V;j++){//正向遍历背包容量dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[V]<<endl;return 0;
}

有趣的是，这个代码与0-1背包基本一致，只是更改了j的遍历方向。

四、多重背包

1. 朴素做法

多重背包问题与0-1背包问题的最大区别即是第i件物品有c[i]个。

考虑增加一层循环遍历k，将可选c[i]次的物品i分解为c[i]个可选1次的物品i，则该问题被转化为0-1背包问题。状态转移方程显然为dp[j]=max(dp[j-w[i]]+v[i])，其中k从1遍历到c[i]。

需要注意的是，遍历k时正向遍历，且要使k*w[i]<=j，防止下标出现负值；遍历j时应从V到k*w[i]倒序遍历；k应在j外、i内遍历。

部分代码如下（已使用滚动数组优化）：

for(int i=1;i<=n;i++){for(int k=1;k<=c[i];k++){for(int j=V;j>=k*w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}
}

2. 二进制优化

(1) 算法思想

在朴素做法中，我们增加了一层循环遍历k，使得时间复杂度增加到了O(nVΣk)，容易超时。

时间复杂度升到如此之高的原因，正是我们进行了大量重复操作。

举例来说，考虑一个能选3次的体积为w、价值为v的物品，如果使用朴素做法，那么这个物品将被分解为3个能选1次的、体积均为w的、价值均为v的物品。不妨将这3个物品分别标号为p、q、r。

在循环遍历中，我们会重复考虑「选p」「选q」「选r」这3种情况，而p、q、r这3个物品的体积、价值均相等，所以这3种情况在原则上是等价的，不需要被重复考虑，这才产生了麻烦。

回忆曾经的算法课，我们曾学过十进制数的二进制表示方法。比如十进制数7，它在二进制上可以表示为111，即4+2+1。

由于二进制特殊的性质，在二进制上，n个数位的0-1组合所对应的十进制数值总不同（只考虑自然数）。

例如：考虑一个3位二进制数p，它每一位的0-1状态与其对应的数值如下表所示：

第一位	第二位	第三位	十进制数值
0	0	0	0
0	0	1	1
0	1	0	2
0	1	1	3
1	0	0	4
1	0	1	5
1	1	0	6
1	1	1	7

由此，可以得到一个重要结论：在二进制上，n个数位的0-1组合可以表示出0~2^n-1这2n种十进制数值。

进而得到推论：对于任意的十进制正整数w，都可以将它拆分成p+q的形式，其中p=2^n-1，n、q都是自然数，且p≥q。

例如：对于十进制数19，距它最近的p是15（即2^4-1），则q是4，所以19可以被拆分为1+2+4+8+4。按照这种方式拆分，可以用前4个数组合出0_{15的自然数；16}19之间的数则可以通过12~15加上3得到。

这时，我们可以通过枚举c[i]经二进制拆分所拆分出来的数字，来得出每个物品取1~c[i]个的情况。此时的时间复杂度骤降到O(nVΣlogk)。

(2) 例题

洛谷P1776 宝物筛选

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,V,a,b,c,cnt,dp[N],w[N],v[N];
int main(){cin>>n>>V;for(int i=1;i<=n;i++){cin>>a>>b>>c;for(int j=1;j<=c;j<<=1){//二进制分解pv[++cnt]=a*j;w[cnt]=b*j;c-=j;}if(c){//作差qv[++cnt]=a*c;w[cnt]=b*c;}}//接下来就是0-1背包了for(int i=1;i<=cnt;i++){for(int j=V;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);} }cout<<dp[V];return 0;
}