Peter算法小课堂—背包问题

我们已经学过好久好久的动态规划了，动态规划_Peter Pan was right的博客-CSDN博客

那么，我用一张图片来概括一下背包问题。

大家有可能比较疑惑，优化决策怎么优化呢？答案是，滚动数组，一个神秘而简单的东西。

01背包

题目：小偷来你家，他带的包只能装c斤的财务。你家有n种财务，分别重w1、w2......wn斤，价值分别为v1、v2......，请输出能拿走的最大总价值？

大家思考一下状态定义和状态转移方程。

额……

状态定义

f[i][j]：用前i个物品，每个物品只能选或不选，满足重量和小于等于j的所有选法中，价值最高的那个方案。最终答案：f[n][c]

状态转移方程

首先，我们分两种情况讨论：1.选i 2.不选i

1。此时我们重量和会变小w[i]，但是价值会增加v[i]，f[i][j]=f[i-1][j-w[i]]+v[i]

2。此时物品数减1，f[i][j]=f[i-1][j]

最后，再取最大值，得到状态转移方程：f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])

代码①

for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
for(int i=1;i<=n;++i){
	for(int j=1;j<=c;++j){
		if(w[i]>j) f[i][j]=f[i-1][j];
		else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
	}
}
cout<<f[n][c]<<endl;

有点费空间，要开滚动数组

代码②

滚动数组，给大家看个图

我们发现，dp[i][j]这一格，只需要i-1这一行，i-2、i-3……都不需要。题目如果并没有要求中间的状态（比如输出背包的方案），我们就可以将其省略来节省空间的使用。所以我们可以只用一维数组dp[j]来记录数据dp[i][j]的状态，在更新的过程中不断用新的数据dp[j] (dp[i][j]) 覆盖掉旧的数据dp[j]（dp[i-1][j]）。大家听懂了吗？？？

代码呢？

#include <bits/stdc++.h>
using namespace std;
const int MAXC=2009;
int n,c,w,v,f[MAXC];
int main(){
	cin>>c>>n;
	for(int i=1;i<=n;i++){
		cin>>w>>v;
		for(int j=c;j>=w;j--)
			f[j]=max(f[j],f[j-w]+v);
	}
	cout<<f[c]<<endl;
	return 0;
}

大家可能会疑惑，为什么第二层循环要倒着推啊，我给出一个解释。我们每次计算dp[j] (即dp[i][j]) 的时候都会需要dp[j-w[i]] (即dp[i-1][j-w[i]])的值。所以如果我们正序计算，那么dp[j-w[i]]就已经更新了（即用过之前的背包了），与每个背包只能用1次不符。那么，这不就是完全背包要的吗？

完全背包

题目：小偷来你家，他带的包只能装c斤的财务。你家有n种财务，每种数量无限多，分别重w1、w2......wn斤，价值分别为v1、v2......，请输出能拿走的最大总价值？

题解请看01背包，这里只给出代码

cin>>c>>n;
for(int i=1;i<=n;i++){
	cin>>w>>v;
	for(int j=w;j<=c;j++)
		f[j]=max(f[j],f[j-w]+v);
}
cout<<f[c]<<endl;

分组背包

分组01与普通01的区别就是，分组01有两组策略：1.选择本组的某一件 2.一件不选

所以说，分组背包编码很麻烦

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll G=19;
const ll N=39;
const ll MAXV=209;
ll c,n,g,f[MAXV];
vector<ll> w[G],v[G]; 
int main(){
	cin>>c>>n>>g;
	for(ll i=1;i<=n;i++){
		ll ww,vv,p;
		cin>>ww>>vv>>p;
		w[p].push_back(ww);
		v[p].push_back(vv);
	}
	for(ll i=0;i<=g;i++){//枚举组号
		for(ll j=c;j>=0;j--){//枚举载重
			for(ll k=0;k<w[i].size();k++){//枚举物品
				if(j>=w[i][k]) f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);
			}
		}
	}
	cout<<f[c]<<endl;
	return 0;
}

多重背包

多重背包怎么办呢，这里，我们要采用二进制拆分。

就是……这样

void bb01(int w,int v){
	for(int j=c;j>=w;j--)
		f[j]=max(f[j],f[j-w]+v);
}
int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>w>>v>>s;
		for(int k=1;k<=s;s-=k;k*=2) bb01(k*w,k*v);
		if(s) bb01(s*w,s*v);
	}
	cout<<f[c]<<endl;
	return 0;
}

简单吧，其实为什么这里我都没有进行仔细的讲解，是因为……不会，再多思考思考01背包和图片。