当前位置:   article > 正文

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

背包问题 多重动态规划

0-1背包问题

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

物品num价值vi重量wi
112
223
354
465

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

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

确定状态: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]=

{dp[i1][j];j<wimax(dp[i1][j],dp[i1][jw[i]]+v[i]);j>=wi
dp[i][j]={dp[i1][j];max(dp[i1][j],dp[i1][jw[i]]+v[i]);j<wij>=wi
在递推求解dp[i][j]过程中会用到前面已计算过的某些值,而每次求解的dp[i][j]都已存到了dp数组中,可直接使用。递推的过程就是一个填表(dp数组)过程。

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

物品num价值vi重量wi
112
223
354
465

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
i\j012345678
0000000000
1001111111
2001223333
3001255677
4001256678

此算法与物品重量顺序无关。由于每一个格子都要填写数字,所以时间复杂度和空间复杂度都是 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;

物品编号价值vi重量wi数量
1121
2231
3542
4653

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

例2(证明每次选价值最高的决策不适用):
C=6;

物品编号价值vi重量wi数量
11051
2832

动态规划(解法一):
注意到多重背包问题跟完全背包是十分相似的,只是多了一个限制每种物品最多选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;

物品编号价值vi重量wi数量
13105
2431
3642
4751

填表:

i/j012345678910
000000000000
100000000003
200044444444
3000466610121212
4000467710121213

最后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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小舞很执着/article/detail/770432
推荐阅读
相关标签
  

闽ICP备14008679号