背包问题

这篇博客主要讲解3个比较简单的背包问题

01背包问题
完全背包问题
多重背包问题

01背包问题
01背包就是有n个物品，你有一个背包可以装体积和为v的物品，同时每个物品都具有价值和体积且只有一件，让你在背包可以装得下的情况下，获得最大的价值。

我们对于每一个物品都有两种决策，装和不装这个物品。
同时我们用 dp[i][j] 表示前 i 个物品，体积为 j 的最大价值。
那么 dp[n][v] 就是我们的答案。

对于每个物品，如果我们不装它，那么dp[i][j] = dp[i-1][j]。因为我们不装就考虑前 i-1个物品就可以了。
相反，如果我们装它，那么dp[i][j] = dp[i-1][j-v] + w。因为我们装这个物品，那么继续考虑前 i-1个物品，同时，可用体积减去这个物品的体积，价值加上这个物品的价值。

#include<bits/stdc++.h>
using namespace std;
int N,V,v,w,dp[1001][1001];
int main()
{
	cin>>N>>V;
	for(int i=1;i<=N;i++)
	{
		cin>>v>>w;
		for(int j=0;j<=V;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j>=v)
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w);
		}
	}
	cout<<dp[N][V]<<endl;
	return 0;
}

这个代码，就是01背包的完全代码，但是并不是最优的，为什么呢？因为浪费了许多空间，我们从状态转移方程可以看出，每个方程只与前 i-1 的状态有关，我们就把dp优化为一维的。怎么优化呢?我们用 dp[j] 表示体积为 j 的情况下，最大的价值。
我们需要变化的就是第二重循环，让我们每次用到 dp[j-v] 的时候都是 i-1 的状态，如果正向枚举很显然是不行的，那么我们就可以反向枚举这样用到 dp[j-v] 时，必然是 i-1 的状态。就有了下面的代码。

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

完全背包问题
基于01背包，不同点就是每件物品不是一件，而是无数件。
有一种比较简单的写法，就是三重循环，第三重循环循环物品的个数，如果可以取就取两个之间的max，如果超过了，背包的最大体积就退出。

#include<bits/stdc++.h>
using namespace std;
int N,V,v,w,dp[1001][1001];
int main()
{
	cin>>N>>V;
	for(int i=1;i<=N;i++)
	{
		cin>>v>>w;
		for(int j=0;j<=V;j++)
		{
			dp[i][j]=dp[i-1][j];
			for(int k=1;k*v<=j;k++)
				dp[i][j]=max(dp[i][j],dp[i-1][j-k*v]+k*w);
		}
	}
	cout<<dp[N][V]<<endl;
	return 0;
}

这是最基础的一种写法，可以解决大部分这种问题，但是并不是最优的。
如果仔细想一下就可以发现我们把01背包的第二重循环反过来就可以得到完全背包的解，为什么呢？
完全背包就是每个物品可以取无数次，如果我反过来循环，循环到后面时，如果有选不仅一次是最优解时，我们通过取max就可以改变。所以有了如下代码：

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

多重背包问题
这个与上面的也很相似，唯一的不同点就是每件物品规定了件数，而不是无数个，也不一定是一个。
同理我们可以三重循环解出。第三重循环枚举每个物品的件数，如果可以取就求max

#include<bits/stdc++.h>
using namespace std;
int N,V,v,w,s,dp[101][101];
int main()
{
	cin>>N>>V;
	for(int i=1;i<=N;i++)
	{
		cin>>v>>w>>s;
		for(int j=0;j<=V;j++)
		{
			dp[i][j]=dp[i-1][j];
			for(int k=1;k<=s&&k*v<=j;k++)
				dp[i][j]=max(dp[i][j],dp[i-1][j-k*v]+k*w);
		}
	} 
	cout<<dp[N][V]<<endl;
	return 0;
}

二进制优化

当然这也不是最优的，因为三重循环时间复杂度是非常大的，那有没有办法降低时间复杂度呢？当然是有的。
我们可以细想一下，多重背包是不是就是如果件数不唯一，我们把件数一件一件拆开，就变成了一个01背包的问题。
这样可以解决对于每个物品，我们可以选 0 到物品个数 s。每一个都可以完成。
如果我们要降低时间复杂度，就可以从这里入手。
我们把件数一件一件拆开，是为了解决我们可以选 0 到物品个数 s ，我们每一个选择都可以完成，那我们其实把物品拆成log(s)向上取整份就行，为什么呢？
我们可以把s写成二进制的形式，如10：1010
我们用1 2 4 3就可以组成 0 到 10 的所有数字
0 = 0
1 = 1
2 = 2
3 = 2 + 1
4 = 4
5 = 4 + 1
6 = 2 + 4
7 = 1 + 2 + 4

在上面的基础再加3，我们就组成了 0 到 10 的所有数字。
如 23
我们用1 2 4 8 8就可以组成。
就有了下面代码

#include<bits/stdc++.h>
using namespace std;
int N,V,v,w,s,dp[2010];
struct node
{
	int v,w;
};
vector<node> goods;
int main()
{
	cin>>N>>V;
	for(int i=1;i<=N;i++)
	{
		cin>>v>>w>>s;
		for(int j=1;j<=s;j*=2)
		{
			s-=j;
			goods.push_back({v*j,w*j});
		}
		if(s)	goods.push_back({v*s,w*s});	
	}
	for(vector<node>::iterator x=goods.begin();x!=goods.end();x++)
	{
		for(int i=V;i>=x->v;i--)
			dp[i]=max(dp[i],dp[i-x->v]+x->w);
	}
	cout<<dp[V]<<endl;
	return 0;
}