动态规划------背包问题详解

一、01背包

有n件物品，每件物品占用的空间为w[i], 价值为p[i]。
有容量为 V 的背包。求在容量允许的范围下，背包装入物品的最大价值。

例如有5件物品，容积为10，五件物品的体积和价值分别为（1,5）（2,4）（3,3）（4,2）（5,1）

下边用表格来枚举所有情况：

---

用dp[i][j]表示前i件物品容积为j是可以装入的最大价值，考察第i件物品时有两种情况。

1. 如果i物品的体积大于v，装不下了。就只能放弃。则最大价值不变。dp[i][v] = dp[i-1][v];
2. 如果i物品的体积不大于v，可以选择装入i或者不装入i。

• 如果装入i，则剩余的容量变为v-w[i]。整个问题变为，先把i装入，再用v-w[i]的空间去装前i-1件物品。 dp[i][v] = dp[i-1][v-w[i]] + p[i]
• 如果不装入i，则dp[i][v] 依然是dp[i-1][v]。和情况1相同。

下面是代码

#include <iostream>
using namespace std;
int dp[35][250];//dp[i][j]表示容量为j前i个物品最大价值 
int m,n,w[35],c[35];//m容量 n物品 w重量 c价值 
int main()
{	
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(w[i]<=j)//可以装第i个 
				dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+c[i]);
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

• 但这是二维数组，还可以进行优化，因为每次dp[i][j]都是与上一次有关，所以可以将数组优化为一维

这是一维数组初始状态，

• 为什么体积为10的时候没有算呢？因为在算体积为10的时候，当前物品体积为5，如果加入，那么剩余体积为5，剩余体积为5的状态已经计算过，加起来就是2，而实际应该是1才对，这样顺序计算显然是有问题的

• 计算dp[v]的时候，应保证dp[ v -w[i] ]依然等于dp[i-1][ v-w[i] ]。
  但是这样顺序计算的话，明显不对。因为v是从小到大计算，dp[ v-w[i]] 已经在 dp[v]之前被计算过了。我们用到的 dp[ v-w[i] ] 是第i次循环计算出来的值。

• 我们的代码相当于在执行：dp[ i ][ v ] = max{ dp[ i-1 ][ v ],dp[ i ][ v-w[i] ] }; (注意是dp[ i ][ v-w[i] ])

• 为了保证先计算dp[v]，需要颠倒一下计算顺序。

初始化细节：

• 如果题目要求背包装满 dp[0]=0，其余赋值-INF；
• 如果不要求装满，全初始化为 0；

最终代码：

#include <iostream>
using namespace std;
int dp[250];
int m,n,w[35],c[35];//m容量 n物品 w重量 c价值 
int main()
{	
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=1;j--)
		{
			if(j>=w[i])//可以装第i个 
			{
				dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			}
		}
	}
	cout<<dp[m]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

二、完全背包

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

完全背包就是把能放多少个i物品的情况都遍历更新一遍，直到背包容量不够。dp[i][j]=max(dp[i-1][j-k×i的重量]+k×i的价值)(k>=0),至于k能增加到多少，就看什么时候到达上限

---

for(int i=1; i<=n; i++)
 {												
 	for (int j=0; j<=v; ++j)
    {
        for(int k=0; k*w[i]<=j; k++)
        {
              dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*c[i]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10

优化：

• 因为同种物品可以多次选取，那么第i种物品最多可以选取V/w[i]件价值不变的物品，然后就转化为01背包问题。
• 如果把第i种物品拆成体积为w[i]×2k价值c[i]×2k的物品，其中满足w[i]×2k≤V。即设dp[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。那么对于第i种物品的出现，我们对第i种物品放不放入背包进行决策。如果不放那么dp[i][j]=dp[i-1][j]；如果确定放，背包中应该出现至少一件第i种物品，所以dp[i][j]种至少应该出现一件第i种物品,即dp[i][j]=dp[i][j-w[i]]+c[i]。
• 为什么是dp[i][j-w[i]]+c[i]？因为dp[i][j-w[i]]里面可能有第i种物品，也可能没有第i种物品。我们要确保dp[i][j]至少有一件第i件物品，所以要预留w[i]的空间来存放一件第i种物品。dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+c[i]);因为第i件物品可以取无数个所以dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+c[i])就是在寻找第i件物品取多少件时最优。

公式推导一下：

dp[i][j]=dp[i-1][j-k*w]+k*c 
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+c,dp[i-1][j-2*w]+2*c+dp[i-1][j-3*w]+3*c....) 
dp[i][j-w]=max(         dp[i-1][j-w],  dp[i-1][j-2*w]+c+  dp[i-1][j-3*w]+2*c....)

dp[i][j]=max(dp[i-1][j],dp[i][j-w]+c)
1
2
3
4
5

---

代码实现：

for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(w[i]<=j)//可以装第i个 
				dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+c[i]);//这里与01背包不同
1
2
3
4
5
6
7

0-1背包和完全背包的不同：

1. 从二维数组上区别0-1背包和完全背包也就是状态转移方程就差别在放第i中物品时，完全背包在选择放这个物品时，最优解是dp[i][j-w[i]]+c[i]即画表格中同行的那一个，而0-1背包比较的是dp[i-1][j-w[i]]+c[i]，上一行的那一个。

2. 从一维数组上区别0-1背包和完全背包差别就在循环顺序上，0-1背包必须逆序，因为这样保证了不会重复选择已经选择的物品，而完全背包是顺序，顺序会覆盖以前的状态，完全背包需要的也就是01背包需要避免的地方，所以存在选择多次的情况，也符合完全背包的题意。状态转移方程都为dp[j] = max(dp[j],dp[j-w[i]]+c[i])。

初始化细节：

• 如果题目要求背包装满 dp[0]=0，其余赋值-INF；
• 如果不要求装满，全初始化为 0；

将二维转为一维：

#include <iostream> 
using namespace std;
int main()
{
	int m,n;
	int w[35],c[35];//w重量 c价值
	int dp[205]={0};
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>c[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]]+c[i]);
		}
	}
	cout<<"max="<<dp[m]<<endl; 

	return 0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

三、多重背包

有N种物品和一个容量为V的背包，第i种物品的费用是c[i]，价值是w[i]，数量为s[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

最容易想到的方法就是和最开始求完全背包时一样，直接暴利转化，枚举可以取多少个。

---

下面看代码：

#include <iostream>
using namespace std;
int main()
{
	int n,m;
	int v[505],w[505],s[505],dp[6005];
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>v[i]>>w[i]>>s[i];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=m;j>=v[i];j--)
		{
			for(int k=0;k<=s[i];k++)
			{
				if(j>=k*v[i])
				{
					dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
				}
			}
		}
	}
	cout<<dp[m]<<endl;
	
	return 0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

但这样如果数量太多，效率就会很低，优化方法就是采用二进制优化

• 运用二进制，进行物品拆分，转化为01背包。
• 比如：13个相同的物品可以分为四组（1,2,4,6），用这四组可以组成任意一个1-13之间的数。
• 原理：一个数总可以用2^k表示
• 而且总和等于13，所以不会组成超过13的数。
• 所以可将一种有C个的物品拆分成：1,2,4,8,16…2 ^(k-1),C-2 ^(k-1),然后转化为01背包问题

二进制优化后的代码

 #include <iostream>//二进制优化 
 using namespace std;
 int main()
 {
 	int n,m,v,w,s,dp[6005]={0};
 	int price[6005],value[6005],k=0;
 	cin>>n>>m;
 	for(int i=0;i<n;i++)
 	{
 		cin>>v>>w>>s;
 		for(int j=1;j<=s;j<<1)
 		{
 			price[++k]=j*v;//存体积 
 			value[k]=j*w;//存价钱 
 			s-=j;
		 }
 		if(s)
 		{
 			price[++k]=s*v;
 			value[k]=s*w;
		 }
 		
	 }
	 for(int i=1;i<=k;i++)
	 {
	 	for(int j=m;j>=price[i];j--)
	 	{
	 		dp[j]=max(dp[j],dp[j-price[i]]+value[i]);
		 }
	 }
	cout<<dp[m]<<endl;
 	
 	return 0;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

四、二维费用背包

对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值(比如,背包容量、最大承重)，求怎样选择物品可以得到最大的价值。

• 设第i件物品所需的两种代价分别为a[i]和b[i]，两种代价可付出的最大值(比如体积和重量)分别为V和U，物品的价值为w[i]。对应算法:费用加了一维，只需状态也加一维即可!

• 设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值，状态转移方程则为:

f[i][v][u]=max{f[i-1][v][u],f[i-1][v- a[i]][u-b[i]] +w[i]}
1

这个是二维费用01背包问题，相应的完全背包、多重背包也是只需要加一维即可