北海做网站哪家好google广告投放

上算法课的时候学到了背包问题。嗯，又是熟悉的配方，今天来复习一下。

 

一、完全背包问题：

问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。

第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

 

和之前做过的LeetCode322,零钱兑换（https://blog.csdn.net/qq_40636117/article/details/80941638）很像，

只不过那题要求用最少数量的硬币来找零，而完全背包问题求的是价值总和最大。

不过思路还是一样的：设容量为n时容纳最大价值为dp[n]

背包容量价值=某物品价值+剩下空间容纳最大价值。

如果背包容量为n,那么 dp[n] = v[i]+dp[n-w[i]]

满足上述条件的i肯定不止一个，找出所有的i,计算v[i]+dp[n-w[i]]的最大值即可

 

例题分析

物品编号   0    1    2    3 
重量w      7    4    3    2  
价值v      9    5    3    1  求背包容量=7时，背包容纳的最大价值1.容量=0：毛都装不下，∴dp[0];2.容量=1：还是毛都装不下，∴dp[1]=0;3.容量=2：（1）∵2=w[2]+0,∴方案1=v[2]+dp[0]=1只有一种方案，∴dp[2]=方案1=1；4.容量=3：（1）∵3=w[3]+1,∴方案1=v[2]+dp[1]=1（2）∵3=w[2]+0,∴方案2=v[2]+dp[0]=3dp[3]=max(方案1，方案2）=35.容量=4：（1）∵4=w[1]+0,∴方案1=v[1]+dp[0]=5（2）∵4=w[2]+1,∴方案2=v[2]+dp[1]=3（3）∵4=w[3]+2,∴方案3=v[3]+dp[2]=2dp[4]=max(方案1,2,3）=56.容量=5：（1）∵5=w[1]+1,∴方案1=v[1]+dp[1]=5（2）∵5=w[2]+2,∴方案2=v[2]+dp[2]=4（3）∵5=w[3]+3,∴方案3=v[3]+dp[3]=4dp[5]=max(方案1,2,3）=57.容量=6：（1）∵6=w[1]+2,∴方案1=v[1]+dp[2]=6（2）∵6=w[2]+3,∴方案2=v[2]+dp[3]=6（3）∵6=w[3]+4,∴方案3=v[3]+dp[4]=6dp[6]=max(方案1,2,3)=68.容量=7：（1）∵7=w[0]+0,∴方案1=v[0]+dp[0]=9（2）∵7=w[1]+3,∴方案2=v[1]+dp[3]=8（3）∵7=w[2]+4,∴方案3=v[2]+dp[4]=8（4）∵7=w[3]+5,∴方案4=v[3]+dp[5]=6dp[7]=max(方案1,2,3,4)=9由上面一波分析，即可求出背包容量=7时，最多容纳dp[7]=9价值的物品

 

代码

	//完全背包问题（物品无穷）static int KnapSack1(int w[],int v[],int sp){int dp[]=new int[sp+1];dp[0]=0;for(int i=1;i<dp.length;++i){int MaxVal=0;for(int j=0;j<w.length;++j){if(i-w[j]>=0){if(MaxVal < dp[i-w[j]]+v[j] ){MaxVal = dp[i-w[j]]+v[j];}}}dp[i]=MaxVal;}return dp[sp];}

二、0/1背包问题

问题：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。

 

这题和前面大体一致，不同的是每个物品只能拿一个（所以称为0/1背包问题）。

这题比上面的题目更加复杂，主要表现在物品只能拿一次，所以还得给物品做去重复的判断。

 

很自然，我们可以开一个二维的数组进行辅助标记，用来标识物品是否被使用过。不过这种做法很不动态规划。

我想起做LeetCode518,零钱兑换Ⅱ（https://blog.csdn.net/qq_40636117/article/details/85219168）时也遇到了相同的问题，题目求的是找钱的方案，也要去掉重复。当时通过对硬币和找零都做动态规划，使得方案防止了重复。

 

回到这个问题，我们先把物品0装进去，计算容量0~m时，背包容纳的最大价值；

然后把物品1装入，同样求出容量0~m时，背包容纳最大价值。。。

 

假设当前装入n号物品g[n]，且容纳空间为m：

①w[n]>m：物品无法被装入，物品m不会对之前的状态产生影响，∴dp[n][m]=dp[n-1][m]

②w[n]<=m：说明能装入物品。这时可以像完全背包问题时那样分析了：

装入g[n]前最大价值为 dp[n-1][m],

装入g[n]后最大价值为 dp[n-1][m-w[n]]+v[n],比较两者大小即可

（装入g[n]的意思是先从背包里倒出一些东西，腾出w[n]大小的空间，然后再把w[n]装进去）

∴dp[n][m]=max(dp[n-1][m],dp[n-1][m-w[n]]+v[n])

要注意的是g[0]这种情况，因为如果用上面方法的话会出现dp[0-1][m]的情况，对于此要进行特殊判断

例题：
物品g   0    1    2    3   
重量w   2    2    4    1
价值v   2    3    9    2
每个物品只能拿一次，求容量为5时背包容纳物品最大价值dp[0]    dp[1]    dp[2]    dp[3]    dp[4]    dp[5]g[0]    0       0        2        2        2        2g[1]    0       0        3        3        5        5g[2]    0       0        3        3        9        9g[3]    0       2        3        5        9        11

 

代码：

	//01背包问题（物品不重复）static int KnapSack2(int w[],int v[],int sp){int dp[][]=new int[w.length][sp+1];for(int i=0;i<w.length;i++){for(int j=0;j<=sp;++j){if(i>0){//一般情况：物品0~物品nif(j<w[i]){dp[i][j]=dp[i-1][j];}else{dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}}else{//特殊情况：物品0if(j>=w[i]){dp[i][j]=v[0];}}}}return dp[w.length-1][sp];}