专栏文章

C++算法讲解：背包DP

LLittle_Zyl
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min9pccw
此快照首次捕获于
2025/12/01 22:51
3 个月前
此快照最后确认于
2025/12/01 22:51
3 个月前
查看原文
取舍之间，方显智慧。 ——《权书·强弱》
注：本文中所有分析中都以nn为物品数量,mm为背包容量,wiw_{i}为物品重量或体积,viv_{i}为物品价值。

一、0-1背包：P1048 采药

题意

你现在有 mm(原TT) 的时间在山洞里采药，总共有 nn(原mm) 株草药，每株草药都有采摘它所需的时间和它的价值，让采到的草药的总价值最大。

思路

我们可以将这个问题抽象成这样：你有一个容量为mm的背包，总共有nn个物品，每个物品都有它的体积wiw_i与价值viv_i，让装进背包的物品的总价值最大。这就是所谓的0-1背包(因为此时每个物品都只有选与不选两种状态)，在这上面进行修改与变形，就有了其他种类的背包。显然背包问题可以用DP解决。
对于0-1背包，我们设dpjdp_j为容量为jj的背包中能获得的最大价值。第一重循环枚举所有物品，第二重循环枚举所有能放下该物品的背包(即容量为wiw_i~mm的背包)，而该背包若选择此物品所能得到的最大价值即为容量比这个背包少wiw_i的背包能装下的最大价值加上该物品的价值viv_i，然后取maxmax就行了。于是我们可以得到状态转移方程为：
                
但是，我们还要保证每种物品只能选一次，其实只需要将第二重循环所枚举的背包容量从大到小枚举就行了。这样，每次更新都只会访问到在上一个物品时更新的值，而不会访问到在这个物品时更新的值，因为每次更新都只会访问到下标比自己小的。

完整代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m,dp[N],w[N],v[N];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
	for(int i=1;i<=n;i++)
		for(int j=m;j>=w[i];j--)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	cout<<dp[m];
	return 0;
}
AC记录

二、完全背包：P1616 疯狂的采药

题意

依旧是采药，但这次是nn(原mm)种草药，每种草药有无数株。

思路

抽象一下：你有一个容量为mm的背包，总共有nn种物品，每种物品都有它的体积wiw_i与价值viv_i，且每种物品有无数个，让装进背包的物品的总价值最大。这就是完全背包。
其实只需要将上一题中第二重循环的从大到小枚举改为从小到大枚举就行了。因为0-1背包需要保证每个物品只拿一次，不能访问到用当前物品所更新的值，而在完全背包中，可以无限拿，恰恰又需要访问到用当前物品所更新的值，所以要从小到大枚举。

完整代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e4+5,M=1e7+5;
int n;ll m,dp[M],w[N],v[N];
int main(){
    cin>>m>>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<=m;j++)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    cout<<dp[m];
    return 0;
}
AC记录

三、分组背包：P1757 通天之分组背包

题意

这里的背包在0-1背包的基础上多了一条限制：所有物品被分为了kk组，组内的物品相互冲突，即每组物品中只能拿一个。

思路

像这样组内的物品相互冲突的背包就被称为分组背包。
不难想到，只需要将第一重循环改为枚举每个组，然后再加一层循环来枚举每组内的每组物品；也不难想到，枚举组内物品的循环应放在枚举背包容量的循环内，因为如果是枚举每组后立即枚举组内物品就会等效于依次枚举每个物品，就和原来的0-1背包没区别了；依旧不难想到，原来0-1背包中的容量从大到小枚举就已经保证了每个组内的物品只会选一次，因为每次更新答案都只会访问容量比自己小的背包。

完整代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
struct stru{int w,v;};
vector<stru>a[N];
int n,m,dp[N];
int main(){
	cin>>m>>n;
	for(int i=1,w,v,id;i<=n;i++)
		cin>>w>>v>>id,a[id].push_back({w,v});
	for(int i=1;i<=n;i++)
    	for(int j=m;j>=0;j--)
    	    for(auto e:a[i])
    	        if(j>=e.w)dp[j]=max(dp[j],dp[j-e.w]+e.v);
    cout<<dp[m];
	return 0;
}
AC记录

四、多维背包：P1794 装备运输

题意

依旧是一个背包和nn个物品，但这次，背包有了最大体积m1m1与最大重量m2m2两个限制，而每个物品的属性也变为了价值vv、体积w1w1和重量w2w2。

思路

像这样有多个限制条件的背包即为多维背包，因为此时的dp数组就要多出一维来保证多出来的一层限制条件，循环也要多出一层来枚举第二重限制条件，其余的与0-1背包一样。

完整代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m1,m2,v[N],w1[N],w2[N],dp[N][N];
int main(){
	cin>>m1>>m2>>n;
	for(int i=1;i<=n;i++)cin>>v[i]>>w1[i]>>w2[i];
	for(int i=1;i<=n;i++)
		for(int j1=m1;j1>=w1[i];j1--)
			for(int j2=m2;j2>=w2[i];j2--)
				dp[j1][j2]=max(dp[j1][j2],dp[j1-w1[i]][j2-w2[i]]+v[i]);
	cout<<dp[m1][m2]; 
	return 0;
}
AC记录

五、依赖背包：P1064 金明的预算方案

题意

依旧是容量为mm的背包，nn个拥有价格ww和价值vv，但是此时的nn个物品分为了主件和附件，每个附件都需要先装其对应的主件，但是每个主件有且仅可能有00个、11个或22个附件。每个附件只对应一个主件，附件不再有从属于自己的附件。

思路

发现每个主件所拥有的附件并不多，且附件不再有从属于自己的附件，所以我们可以直接把枚举每个物品改为枚举每个主件，对于每个主件直接依次枚举四种情况：
  1. 只买这个主件；
  2. 买这个主件和它的第一个附件；
  3. 买这个主件和它的第二个附件；
  4. 买这个主件和它的所有附件。
注意特判每种情况当前容量的背包是否装的下。

完整代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1e5+5;
int n,m,w[N][3],v[N][3],dp[M];
int main(){
	cin>>m>>n;
	for(int i=1,tw,tv,p;i<=n;i++){
		cin>>tw>>tv>>p;
		if(!p)w[i][0]=tw,v[i][0]=tv*tw;
		else if(!w[p][1])w[p][1]=tw,v[p][1]=tv*tw;
		else w[p][2]=tw,v[p][2]=tv*tw;
	}
	for(int i=1;i<=n;i++){
		if(!w[i][0])continue;
		for(int j=m;j>=w[i][0];j--){
			dp[j]=max(dp[j],dp[j-w[i][0]]+v[i][0]);
			if(j>=w[i][0]+w[i][1])
				dp[j]=max(dp[j],dp[j-w[i][0]-w[i][1]]+v[i][0]+v[i][1]);
			if(j>=w[i][0]+w[i][2])
				dp[j]=max(dp[j],dp[j-w[i][0]-w[i][2]]+v[i][0]+v[i][2]);
			if(j>=w[i][0]+w[i][1]+w[i][2])
				dp[j]=max(dp[j],dp[j-w[i][0]-w[i][1]-w[i][2]]+v[i][0]+v[i][1]+v[i][2]);
		}
	}
	cout<<dp[m];
	return 0;
}
AC记录

六、多重背包：P1776 宝物筛选

题意

容量为mm的背包，nn种拥有价格ww和价值vv的物品，每种物品只有slsl个(最多选slsl次)。

思路

这里给出二进制优化的做法。
首先，我们发现其实可以将每种物品看做有slsl个这样的物品，然后直接做0-1背包。但是，从数据范围中发现，∑sli\sum sl_i(原题中为∑mi\sum m_i)有整整10510^5。所以我们要考虑优化。
进一步分析得到，我们可以将每种物品的slsl拆分为几个数，然后只要保证这几个数能表示出11~slsl中的所有数就行了。于是我们就想到了二进制，所以这几个数就分别为相加小于等于该数的2的幂次方和那个数与和的差值。举个栗子，我们用上述方法可以将1919拆分为 1,2,4,8,31,2,4,8,3，不难发现，这五个数可以组成11至1919中的所有数。最后，用该种物品的ww和vv分别乘上这几个数形成几个新的物品后就能做0-1背包了。

完整代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,wz,w[N],v[N],dp[N];
void ycl(int tw,int tv,int sl){
    for(int x=1;sl>x;sl-=x,x*=2)
        w[++wz]=x*tw,v[wz]=x*tv;
    w[++wz]=sl*tw,v[wz]=sl*tv;
}
int main(){
    cin>>n>>m;
    for(int i=1,tw,tv,sl;i<=n;i++)
        cin>>tv>>tw>>sl,ycl(tw,tv,sl);
    for(int i=1;i<=wz;i++)
        for(int j=m;j>=w[i];j--)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    cout<<dp[m];
    return 0;
}
AC记录

总结

这里介绍了六种最基本的背包DP问题，其实也不难发现，后面五种都是0-1背包的变形与升级。当然还有许多像树形背包、最优比率背包等进阶背包，这里就不一 一讲解了。背包DP在信息竞赛中也是比较常考的算法，需要大家的掌握。最后也推荐大家去做一下这张题单(From BackSlashDelta)，里面包括了一些必做背包DP的入门题目和一些好题。
那么这篇博客到这就结束了，感谢大家的阅读！！！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...