当前位置:   article > 正文

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

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

一、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]都是与上一次有关,所以可以将数组优化为一维

这是一维数组初始状态,

(V,C)012345678910
000000000000
当第一个物品加入状态变为
(V,C)012345678910
00000111111
  • 为什么体积为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背包问题,相应的完全背包、多重背包也是只需要加一维即可

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

闽ICP备14008679号