动态规划-01背包/完全背包/多重背包问题详解_背包问题 多重动态规划

0-1背包问题

给定一组多个（n）物品，每种物品都有自己的重量（wi）和价值（vi），在限定的总重量/总容量（C）内，选择其中若干个（也即每种物品可以选0个或1个），设计选择方案使得物品的总价值最高。
eg:
背包容量C=8,

贪心算法无法得到最优解。 易举反例。

动态规划：
（本质是状态的记录和转移。具有记忆性，将子问题的解都记录下来，避免重复计算。空间换时间。）

确定状态：dp[i][j] 表示只考虑n件物品中的前i件物品中，在背包承重为j的前提下，能拿到的最大价值。
如dp[3][8] 即表示前3件物品中在背包容量为8的前提下能拿到的最大价值。最终要求的就是dp[n][C] 。
状态边界值： dp[i][0]=0; dp[0][j]=0;
状态转移： 从简单的dp[1][1]等开始，递推算出最终结果。
对于dp[i][j], 即拿第i件物品时，有以下情况：
(1)背包放不下，即j < w[i], 此时dp[i][j]=dp[i-1][j]，即在背包容量为j的前提下，前i件物品和前i-1件物品能拿到的最大价值时一样的。
(2)背包装得下，即j >= w[i], 此时就需要考虑到底拿不拿，因为拿可能就需要把背包中已有的物品取出，这时就要判断哪种情况的价值更大。不拿的话还是dp[i][j]=dp[i-1][j]，拿的话dp[i][j]=dp[i-1][j-w[i]]+v[i];，即除第i件占的容量以外，在剩下的容量j-w[i]的前提下，前i-1件物品能拿到的最大价值。最终是取最大价值的情况，即dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i];。
综上得到状态转移方程为：
d p [ i ] [ j ] = { d p [ i − 1 ] [ j ] ; j < w i m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) ; j > = w i dp[i][j]=

$$\begin{cases} dp[i-1][j]; & j < wi \\ max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); & j >= wi \\ \end{cases}$$ dp[i][j]={dp[i−1][j];max(dp[i−1][j],dp[i−1][j−w[i]]+v[i]);​j<wij>=wi​
在递推求解dp[i][j]过程中会用到前面已计算过的某些值，而每次求解的dp[i][j]都已存到了dp数组中，可直接使用。递推的过程就是一个填表（dp数组）过程。

下面我们对一个例子进行动态规划过程的演示：

C=8；
递推填表算法：

for j=0 to C
	dp[0][j] = 0
for i=1 to n
	dp[i][0] = 0
for i=1 to n
	for j=1 to C
		if(j<w[i])
			dp[i][j]=dp[i-1][j]
		else
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
1
2
3
4
5
6
7
8
9
10

此算法与物品重量顺序无关。由于每一个格子都要填写数字，所以时间复杂度和空间复杂度都是 O(nC)。
完整代码：

#include<iostream>
#include<algorithm>
using namespace std;
void solve();
int n,C;
int W[100]={0};
int V[100]={0};
int dp[100][100]; //dp[n+1][C+1]
 
int main()
{
	int i,j;
	cin>>n>>C;
	for(i=0;i<=n;i++) dp[i][0]=0;
	for(j=0;j<=C;j++) dp[0][j]=0;
	for(i=1;i<=n;i++) cin>>W[i]>>V[i];
	solve(); 
}
 
void solve()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=C;j++)
		{
			if(j<W[i]) dp[i][j]=dp[i-1][j];
			else dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+V[i]);
		}
	}
	cout<<dp[n][C]<<endl;
}
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

输出最优解路径：
0/1背包问题之动态规划法求最优解和最优解路径

空间优化

对于上述算法，每一次dp[i][j]改变的值只与dp[i-1][x] {x:1...j}有关，dp[i-1][x] 是前一次i循环保存下来的值；因此，可以将dp缩减成一维数组，从而优化空间。这种做法比较适合只求最大价值的需求。当需要输出最佳方案时，我们常常要回溯历史信息，这时，一般就只能用二维数组这种保存有各个状态值的方法了。

对于空间优化的动态规划算法，其状态的确定以及状态转移会跟原来有些差异。这里确定的状态dp[j]表示背包的容量为j时能拿到的最大价值。优化后的状态转移方程变为
dp[j]=max(dp[j],dp[j-w[i]]+v[i]); 对于状态dp[j],在背包中放了物品之后状态会发生转移，即在此方程中，dp[j]需要由dp[j-w[i]]来推导，因此递推填表的顺序需要调整，j从C到0循环，否者前一次循环保存下来的值将会被修改，从而造成错误。对于物品数量还是从1到n来递推，即整体还是从小问题推大问题。
优化前的填表过程：

for j=0 to C
	dp[0][j] = 0
for i=1 to n
	dp[i][0] = 0
for i=1 to n
	for j=1 to C
		if(j<w[i])
			dp[i][j]=dp[i-1][j]
		else
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
1
2
3
4
5
6
7
8
9
10

优化后：

for j=0 to C
	dp[j] = 0
for i=1 to n
	for j=C to 0
		if(j>=w[i])
			dp[j]=max(dp[j],dp[j-w[i]]+v[i])
1
2
3
4
5
6

完全背包问题

给定一组多个（n）物品，每种物品都有自己的重量（wi）和价值（vi），在限定的总重量/总容量（C）内，选择其中若干个，每种物品都可以挑选多件，设计选择方案使得物品的总价值最高。

贪心算法也不适用。
此问题与01背包问题相似，我们还是确定状态dp[i][j]表示只考虑n件物品中的前i件物品中，在背包承重为j的前提下，能拿到的最大价值。在01背包问题的基础上，我们进一步考虑当j>=w[i]时，此时对于第i件物品，容量j可能不止装得下一件，因此我们在状态dp[i][j]的计算中选择k(k>=1)个 i 物品的情况，与在状态dp[i][j-w[i]]的计算中选择k-1的情况是相同的，所以dp[i][j]的递推中k>=1部分的计算已经在dp[i][j-w[i]]的计算中完成了。因此可得到状态转移方程为：
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);

这样就可得到完全背包问题的动态规划算法：

#include<iostream>
#include<algorithm>
using namespace std;
void solve();
int n,C;
int W[100]={0};
int V[100]={0};
int dp[100][100]; //dp[n+1][C+1]
 
int main()
{
	int i,j;
	cin>>n>>C;
	for(i=0;i<=n;i++) dp[i][0]=0;
	for(j=0;j<=C;j++) dp[0][j]=0;
	for(i=0;i<n;i++) cin>>W[i]>>V[i];
	solve(); 
}
 
void solve()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=C;j++)
		{
			if(j<W[i]) dp[i][j]=dp[i-1][j];
			else dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
		}
	}
	cout<<dp[n][C]<<endl;
}
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

空间优化
我们同样可以对该算法进行空间优化，使用一维数组表示状态转移。与01背包的 空间优化不同的是，这里的内循环j需要正向遍历：

for j=0 to C
	dp[j] = 0
for i=1 to n
	for j=0 to C
		if(j>=w[i])
			dp[j]=max(dp[j],dp[j-w[i]]+v[i])
1
2
3
4
5
6

多重背包问题

给定一组多个（n）物品，每种物品都有自己的重量（wi）和价值（vi），在限定的总重量/总容量（C）内，选择其中若干个，每种物品最多选mi件，设计选择方案使得物品的总价值最高。

贪心算法同样无法求得最优解。
举个例子（证明每次选性价比最高的物品的贪心决策不适用）：
C=8;

性价比最高的是1号物品，只有一个，然后是2号，选这俩之后重量为5，没法再选，但选2个3号才是最优的。

例2（证明每次选价值最高的决策不适用）：
C=6;

动态规划（解法一）：
注意到多重背包问题跟完全背包是十分相似的，只是多了一个限制每种物品最多选m[i]件，如果所有m[i]都满足m[i] ≥ C / w[i]，那就变成了完全背包的问题。因此可以将完全背包的实现思路用到多重背包上。不同就在于物品的个数上界不再是C/w[i]而是m[i]与C/w[i]中较小的那个。所以我们要在完全背包的基本实现之上，再考虑这个上界问题。
递推填表过程与完全背包的填表过程几乎相同，当j<w[i]时，依然是dp[i][j] = dp[i-1][j];，

考虑当j>=w[i]时，这时会出现j > m[i] * W[i]的情况，即第i个物品的数量不够填满j容量的包，因此这个范围内的j对应的能拿到的最大价值是dp[i][m[i] * W[i]]（容量为m[i] * W[i]时前i种物品拿到的最大价值。第i个物品可取0~m[i]个，dp[i][m[i] * W[i]]就表示在所有这些情况里取容量为m[i] * W[i]时前i种物品拿到的最大价值）加上dp[i-1][j-m[i]*W[i]]（除装第i个物品外剩下的空间对应的前i-1种物品拿到的最大价值）。当然，如果第i种物品一个都不拿，则dp[i][j] = dp[i - 1][j],即：
dp[i][j] = max(dp[i - 1][j], dp[i][m[i] * W[i]] + dp[i-1][j-m[i]*W[i]]);

剩下的情况就是w[i]=<j<=m[i] * W[i]，这就与完全背包一模一样了：
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);

下面举个例子：
C=10;

填表：

最后dp[4][10] = dp[4][5]+dp[3][5] = 7+6 = 13;

贴上完整代码：

#include<iostream>
#include<algorithm>
using namespace std;
void solve();
int n, C;
int W[100] = { 0 };
int V[100] = { 0 };
int m[100] = { 0 };
int dp[100][100]; //dp[n+1][C+1]

int main()
{
	int i, j;
	cin >> n >> C;
	for (i = 0; i <= n; i++) dp[i][0] = 0;
	for (j = 0; j <= C; j++) dp[0][j] = 0;
	for (i = 0; i < n; i++) cin >> W[i] >> V[i] >> m[i];
	solve();
}

void solve()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			if (j < W[i]) dp[i][j] = dp[i - 1][j];
			else if (j > m[i] * W[i]) {
				//第i个物品可取0~m[i]个，dp[i][m[i] * W[i]]就表示在所有这些情况里取容量为m[i] * W[i]时前i种物品拿到的最大价值，也就相当于已经考虑了第i个物品取多少个能达到最大价值的所有情况
				//这里稍稍难理解，下图中展开为三重循环的更好理解
				dp[i][j] = max(dp[i - 1][j], dp[i][m[i] * W[i]] + dp[i-1][j-m[i]*W[i]]);
			}
			else{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - W[i]] + V[i]);
			}
		}
	}
	cout << dp[n][C] << endl;
}
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
35
36
37
38
39

解法二：（二进制表示法）
对于多重背包问题，一种巧妙的解法是通过二进制表示法将其转化成01背包问题。即把m[i]分解为m[i]=1+2+4+…+2^k+a的形式，比如物品i有m[i]=7个，每个价值为v[i]=3，重量w[i], 由7 = 1+2+4，则我们把这7个价值是3的物品打了三个包，第一个包里有一个，价值3，重w[i]；第二个包里有两个，价值6，重2w[i]；第三个包里有四个，价值12，重4w[i]；这三个包相当于3个独立的新物品。对于8=1+2+4+1，即分成4个包，最后一个中含一个物品。这样我们就把多重背包的问题转化回了01背包。
代码：

#include<iostream>
#define MAX_N 1000
#define MAX_C 1000
using namespace std;
int n,C;
int w[MAX_N],v[MAX_N],m[MAX_N];
int dp[MAX_C+1];  //全局变量 自动初始化为0
 
int main()
{
	cin>>n>>C;
	for(int i=0;i<n;i++) cin>>w[i]>>v[i]>>m[i];
	for(int i=0;i<n;i++)
	{
		int num=m[i];
		//二进制拆分
		//k从1开始，每次变为原来的2倍
		for(int k=1;num>0;k<<=1)  
		{
			//mul则记录num拆分过程中从小到大的数，由于num不一定刚好能分成若干个2的幂的和,取min(k,num)即可得到num-mul后剩下的余数
			int mul=min(k,num);
			//每拆分依次都会多一个被打包的新物品，因此每次拆分都需要更新再当前前i种物品中容量为j时能拿到的最大价值的值。方法跟01背包是一样的
			for(int j=C;j>=w[i]*mul;j--) dp[j]=max(dp[j],dp[j-w[i]*mul]+v[i]*mul);
			num-=mul;
		}
	}
	cout<<dp[W]<<endl; 
}
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

参考：
https://blog.csdn.net/qq_32400847/article/details/51148917