【动态规划】解析背包dp（更新中，收藏不迷路~~）_背包dp图解

 

背包dp介绍

简单来说就是给一个有一定体积的背包，然后给出一些占体积的物品，需要我们使用dp的方法在相关条件下将物品塞入背包，并达到某些目的（比如物品有价值，得出一定体积背包能得到的最大价值）。

需要的基础：

少量的数学基础（小学水平及以上基本能理解（大概））

对dp思想的一定了解（通过利用已有的子问题信息高效求出当前问题的最优解）

为方便食用，代码无头文件

下面从01背包讲起：

01背包

介绍：该类问题每个物品只有两个可能的状态（取和不取）如二进制一般，所以称为01背包问题。

由一道例题引入：

采药

由于样例给的不太好讲解就自己造了一组：

10 4

3 1

1 2

2 4

3 3

就照着这组数据讲吧：

灵魂图示：（其中花盆（矩形）里的数代表着物品的体积，上面的花（圆圈）里的数代表着价值）

 

不需要先着眼于自己的包多大（因为dp的思想），而是先要考察这些草药能够让某容量的背包装下最大价值的物品（子问题）

只要解决了上述子问题，那么所求问题也解决了~

接下来你开始采药

走到了第一个草药面前

你有将它装入或者不装入背包两种选择

如下表：（第一行代表t容量的背包 第一列代表前i个物品（要注意是前i个不是第i个！））

可知在背包容量大于等于3的时候都可以将①装入，且装入这个选择能取得最大价值（目前）

所以下面我们来更新数据

 

类似地，继续向前走，走到②，进一步更新

如何更新呢，比如说，背包容量小于3（>0）时，只能将②放入，且这样做得到价值是最大的，因此1-3全部加上相应价值2

接下来考察3-10的格子怎么填，注意，所填的格子的状态受到上一行的影响 例如 对于容量为3的背包，如果你考虑上一行的情况 会发现此时背包已经被装满了，那么此时的价值仍然为1。但是，还不可以将1填入格子中，因为你还没有考虑不选择①的情况，此时如果只选择②，你得到的价值为2 这才是最大价值，进行更新。

而对于容量为4的背包 ①②都可以装，更新为3 容量>3的格子也是3（全部拿完）

 

下面的格子自己模拟一下吧，在经过一定的模拟后，你会发现这一点：

对于一个格子的最大价值，有且仅有可能从上一行（即历史的状态）转移而来。

现在给出关键的dp方程：（开二维数组是朴素的想法，因为是直接由上面的表得到的）

dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);

 当然，上面的方程是不完整的，当j<c[i]的时候会越界，所以要加上if-else语句（也请理解一下这样的方程的实际意义）

if(j>=c[i]) 
    dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
else
    dp[i][j]=dp[i-1][j];

下面是code：

int c[101];//物品体积
int w[101];//物品价值
int dp[101][10001]; 
int t,n;//t表示背包容量，n表示物品数量 
int main(){
	cin>>t>>n;
	for(int i=1;i<=n;i++)
	cin>>c[i]>>w[i];
	
	for(int i=1;i<=n;i++){
		for(int j=t;j>=1;j--){
			if(j>=c[i])
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
			else
                dp[i][j]=dp[i-1][j];
		} 
	}
	cout<<dp[n][t];//已经更新完毕，得到答案		
	return 0;
}

 

但是，二维数组是很浪费空间的，注意到状态仅由上一行转移而来，我们想到了一维数组的解法：

这里直接给出关键的方程，请读者认真思考一下这样做的合理性：

dp[j]=max(dp[j],dp[j-c[i]]+w[i]);

 代码：

int c[101];//物品体积
int w[101];//物品价值
int dp[10001]; 
int t,n;//t表示背包容量，n表示物品数量 
int main(){
	cin>>t>>n;
	for(int i=1;i<=n;i++)
	cin>>c[i]>>w[i];
	
	for(int i=1;i<=n;i++){
		for(int j=t;j>=c[i];j--){
			dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
		} 
	}
	cout<<dp[t];		
	return 0;
}

注意！在下面的第二个for中，j应该从t开始倒着扫（和模拟的顺序相反），不然会出现一个物品多次放入的情况！（可以自己打表试试）

（注： 事实上，顺着扫正是下面要讲的完全背包的解法。）

这是倒着扫↓

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

而对于二维的做法则没有倒着扫的必要：

在这里，j从t->1或者从1->t都是合法的，因为都是从上一行转移而来，顺序不影响结果。

for(int i=1;i<=n;i++){
		for(int j=t;j>=1;j--)//for(int j=1;j<=t;j++)亦可
        {
			if(j>=c[i])
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
			else
                dp[i][j]=dp[i-1][j];
		} 
	}

讲完了01背包

下面来讲完全背包

完全背包 

完全背包介绍：

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次（OI wiki）

例题刚好是采药的变式：

疯狂的采药

我们是否仍然能够使用刚才的情境理解呢？可以：

现在你走到第①棵草药面前，开始疯狂地采（采完之后你就不回头了，这样和上面的01背包一样）

那么在你疯狂地采的过程中，你的各种容量的背包会发生什么样的变化呢，依然用表来理解：

你会发现，你的包容积在 3-5 的时候 仍然只能采摘1个 但在6-8时候可以摘2个 以此类推直到考察到t=10的情况

因此，我们可以使用刚才提及的解法

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

code:

 这题范围需要注意 不开long long见祖宗（亲测）

typedef unsigned long long ll;
ll c[10000+5];//物品体积
ll w[10000+5];//物品价值
ll dp[10000000+5]; 
ll t,n;//t表示背包容量，n表示物品数量 
int main(){
	cin>>t>>n;
	for(int i=1;i<=n;i++)
	cin>>c[i]>>w[i];
	
	for(int i=1;i<=n;i++){
		for(int j=c[i];j<=t;j++){
			dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
		} 
	}
	cout<<dp[t];		
	return 0;
}

 

多重背包 

多重背包介绍：

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品 y 有 k个，而非1个(OI wiki)

我们仍然能够使用开头的情境理解：

走到一棵（一丛）草药前 比如①

就是你可以选一棵草药 那么就和01背包更新方式一样 

也可以选两棵 把她们打包成一棵草药（当然价值和体积翻倍）此时，比如开头的第①丛草药对你而言就是一棵 体积3*2 价值1*2的草药，转化成01背包问题进行更新。

类似的，你可以选1-k棵！

理解之后，直接上代码：

int c[101];//物品体积
int w[101];//物品价值
int s[101];//每种物品的数量 
int dp[10001]; 
int t,n;//t表示背包容量，n表示物品种数 
int main(){
	cin>>t>>n;
	for(int i=1;i<=n;i++)
		cin>>c[i]>>w[i]>>s[i];
	
	for(int i=1;i<=n;i++)
		for(int k=1;k<=s[i];k++)
			for(int j=t;j>=k*c[i];j--)
				dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]);
				
	cout<<dp[t];		
	return 0;
}

 

二进制优化

#include<cstdio>
#include<iostream>
using namespace std;
 
int c[100001];//物品体积 cost
int w[100001];//物品价值 wealth
int s[100001];//每种物品的数量 sum
int dp[100001]; 
int t,n;//t表示背包容量，n表示物品种数 
int x1,y1,x2,y2;
int main(){
    scanf("%d:%d %d:%d",&x1,&y1,&x2,&y2);
    if(y1>y2)
    {
        y2+=60;
        x2--;
    }
    t=(x2-x1)*60+y2-y1;//得到时间（背包的容量） 
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>c[i]>>w[i]>>s[i];
	
	for(int i=1;i<=n;i++){
		if(s[i]==0)//考察完全背包 
		{
			for(int j=c[i];j<=t;j++)
				dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
		}
		else//在这里 我将01背包和多重背包一起考察 
		{
			for(int k=1;k<=s[i];k<<=1)//进行二进制分组
			{
				for(int j=t;j>=k*c[i];j--)//可以看成是01背包了 
					dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]);
					
				//记得分组后是可能有剩余的 把它拿出来 
				s[i]=s[i]-k; 
			}
			if(s[i]>0)//对剩余的使用01背包 
			{
				for(int j=t;j>=s[i]*c[i];j--)
					dp[j]=max(dp[j],dp[j-s[i]*c[i]]+s[i]*w[i]);
			} 
		}
	}
			
	cout<<dp[t];
			
	return 0;
}

（更新中）