背包问题是动态规划算法中非常经典的一类问题,也是笔试面试中常见的一类问题。
背包问题有四类:0/1背包问题、完全背包问题、多重背包问题、混合背包问题。
下面将总结0/1背包问题、完全背包问题、多重背包问题三类问题。对于混合背包问题,难度较大,一般笔试面试题也不会过多涉及。
笔者自认为本文将背包问题总结地比较全面,可难免有错漏,欢迎批评指正!
你有一个背包,最多能容纳的重量是m。现在有n个物品,第i个物品的重量为w[i],价值为v[i]。求这个背包至多能装多大价值的物品?
动态规划是一个将大问题划分为小问题进行解决,从而一步步获取最优解的过程。对于0/1背包问题,考虑子问题“求解将前i个物品放入容量为j的背包中的最大价值”,设F(i,j)为将前i个物品放入容量为j的背包中最优解的总价值。对于第i个物品,事实上有两种情况:
(注意理解上述过程:是先比较第i个物品的重量与背包容量,若能放,再比较放入第i个物品与不放入第i个物品哪个能得到前i个物品情况下的最优解!)
因此可以得到递推公式:
$$初始条件:F(i,0)=F(0,j)=0\\$$
和
$$F(i,j)=\begin{cases}F(i-1,j),&w[i]>j\\max\{F(i-1,j),v[i]+F(i-1)(j-w[i])\},&w[i]≤j\end{cases}$$
给出如下一个例子:
背包的承重m=5。现在有4个物品如下,求背包至多能装多大价值的物品:
对于n=4,m=5的背包问题,应建立一个dp[n+1][m+1]的二维表。填表过程如下:
你是否对这个填表过程感到熟悉?是的,所谓背包问题,其实还是前面的二维动态规划问题!
填表过程的代码如下:
是的,本问题的核心思想就是“求解将前i个物品放入容量为j的背包中的最大价值”,而不同的物品顺序显然填出来的表是不相同的。但是,这个动态规划表并不是我们需要的结果,我们也并不关心”前i个物品放入容量为j的背包“的问题,我们关心的是“n个物品放入容量为m的背包”的问题。虽然不同物品顺序得出的动态规划表不一样,但其最优解的值一定是一样的,而这才是我们关心的。
接下来将介绍如何回溯得到最优方案。
我们先用图示的方法看看如何从动态规划表进行回溯、得出最优解的方案:
上述回溯过程似乎很复杂,但是在代码中可以加入一个辅助数组path[][]来记录更新的物品。则求出最优方案的代码如下:
publicstaticvoidknapsack2(int[]w,int[]v,intn,intm){int[][]dp=newint[n+1][m+1];int[][]path=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(w[i-1]>j)dp[i][j]=dp[i-1][j];else{if(dp[i-1][j]
例如将上例中物品1的价值修改为10,求得的最优解虽然同样是35,却存在{物品1,物品2,物品4}和{物品3,物品4}两个最优方案。你可以使用下面两个例子进行测试:
//示例1int[]w={2,1,3,2};//物品的重量int[]v={10,10,20,15};//物品的价值intn=w.length;//物品的个数intm=5;//背包的容量knapsack2(w,v,n,m);//示例2int[]w={3,1,2,2};//物品的重量int[]v={20,10,10,15};//物品的价值intn=w.length;//物品的个数intm=5;//背包的容量knapsack2(w,v,n,m);以上两个例子仅仅交换了物品的顺序,虽然最优解的值相同,但最优方案却不同。
那么,怎么判断最优解的方案是否唯一呢?在填表过程中,如果F[i-1][j]与v[i]+F[i-1][j-w[i]]相等,则可说明存在多个最优方案。
注:此方法不需掌握,可直接跳过。但是看完之后,相信你会对动态规划有更深一步的了解。
动态规划算法是自底向上的:动态规划算法从最小的子问题出发,使用较小子问题的解去填充表格,每个子问题只解一次。但是,有些较小的子问题的解常常不是必需的。
递归的算法是自顶向下的:递归算法对递推式的求解将导致需要不止一次地解公共的子问题。例如斐波那契数列问题,递归算法将多次重复计算相同值,因此效率非常低。
将自底向上的动态规划算法与自顶向下的递归算法结合起来,使它只对必要的子问题求解且只求解一次,这就是记忆功能的方法。该方法自顶向下地使用递归进行求解,但还需维护一个自底向上的动态规划表格:
publicclassMFKnapsackDemo{publicstaticvoidmain(String[]args){int[]w={2,1,3,2};//物品的重量int[]v={12,10,20,15};//物品的价值intn=w.length;//物品的数量intm=5;//背包的容量MFKnapsackmfKnapsack=newMFKnapsack(m,w,v);System.out.println("最大价值为:"+mfKnapsack.knapsack(n,m));}}classMFKnapsack{staticintn;//物品的个数staticintm;//背包的容量staticint[]w;//物品的重量staticint[]v;//物品的价值staticint[][]dp;//动态规划表/***将w[]、v[]、dp[][]作为全局变量*对于dp[][],将第0行、第0列初始化为0,其余全部初始化为-1*/publicMFKnapsack(intm,int[]w,int[]v){this.m=m;this.w=w;this.v=v;this.n=w.length;dp=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){dp[i][j]=-1;}}}publicstaticintknapsack(inti,intj){if(dp[i][j]<0){if(j 对比普通动态规划算法计算出的表格来看,加入记忆功能后,算法将只对必要的子问题进行求解。 回到经典的01背包问题,我们再看一看核心表达式: $$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j\\max\{dp[i-1][j],v[i]+dp[i-1][j-w[i]]\},&w[i]≤j\end{cases}$$ 可以看到,求解dp[i][j]时,其实只需要第i-1行的第j列或者第j-w[i]列的结果,其他行的结果是不需要的。所以我们真正需要的只有i-1这一行,在对i遍历时,第i层可以自动滚动覆盖掉第i-1层。 那么我们就可以进行空间优化,将其优化为一维数组: $$dp[j]=\begin{cases}dp[j],&w[i]>j\\max\{dp[j],v[i]+dp[j-w[i]]\},&w[i]≤j\end{cases}$$ 如果按照这个公式填表,会发现存在以下问题: 出现这个问题的原因是:从左向右遍历会导致,后修改的右边的值需要用到先修改的左边的值。 那么如何解决呢?很简单,将其修改为从右向左遍历即可: 根据填表过程,可以得到01背包问题的空间优化算法: publicstaticintknapsack3(int[]w,int[]v,intn,intm){int[]dp=newint[m+1];for(inti=1;i<=n;i++){for(intj=m;j>=1;j--){//if(w[i-1]>j)dp[j]=dp[j];if(w[i-1]<=j)dp[j]=Math.max(dp[j],v[i-1]+dp[j-w[i-1]]);}}returndp[m];}1.5恰好装满问题你有一个背包,最多能容纳的重量是m。现在有n个物品,第i个物品的重量为w[i],价值为v[i]。若背包恰好装满,求至多能装多大价值的物品?如果无解请返回0。 若使用空间优化,则应初始化dp[0]为0,其余初始化为Integer.MIN_VALUE。 最后若dp[m]为正数则说明恰好装满,若为负数则说明无解。 importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[]v=newint[n];int[]w=newint[n];for(inti=0;i 你有一个背包,最多能容纳的重量是m。现在有n种物品,每种物品有任意多个,第i个物品的重量为w[i],价值为v[i]。求这个背包至多能装多大价值的物品? 我们先看一看经典01背包问题的方程: 对于完全背包问题,由于每种物品有任意多个,那么我们可以再加入一层循环k,k代表第i种物品有k件。 则v[i]应修改为k*v[i],w[i]应修改为k*w[i],且应对遍历的k*v[i]+dp[i-1][j-k*w[i]]取最大值,因此可以得到完全背包问题的方程: $$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j\\max\{dp[i-1][j],max\{k*v[i]+dp[i-1][j-k*w[i]]\}\},&w[i]≤k*w[i]≤j\end{cases}$$ 代码如下: 观察完全背包问题的方程: $$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j&①\\max\{dp[i-1][j],max\{k*v[i]+dp[i-1][j-k*w[i]]\}\},&w[i]≤k*w[i]≤j&②\end{cases}$$ 我们发现,当k=0时,有dp[i-1][j]与k*v[i]+dp[i-1][j-k*w[i]]相等,故以上方程可以合并为: $$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j&①\\max\{k*v[i]+dp[i-1][j-k*w[i]]\},&0≤k≤\frac{j}{w[i]}&②\end{cases}$$ 对于式子②,我们知道有以下两种情况,二者的最大值即为dp[i][j]: $$\begin{aligned}dp[i][j]&=max\{(k+1)*v[i]+f[i-1][j-(k+1)*w[i]]\}\\&=max\{k*v[i]+f[i-1][j-(k+1)*w[i]]\}+v[i]\\&=max\{k*v[i]+f[i-1][j-w[i]-k*w[i]]\}+v[i]\end{aligned}\\(0≤k≤j/w[i])$$ $$dp[i][j-w[i]]=max\{k*v[i]+dp[i-1][j-w[i]-k*w[i]]\}\\(0≤k≤j/w[i])$$ 综合不放入的情况与放入的情况,两者应取最大值,因此式子②可以写为: $$dp[i][j]=max\{dp[i-1][j],dp[i][j-w[i]]+v[i]\}\tag{w[i]≤j}$$ 综上,结合式子①与式子②,因此完全背包问题的方程为: $$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j\\max\{dp[i-1][j],dp[i][j-w[i]]+v[i]\},&w[i]≤j\end{cases}$$ 因此可以写出代码: publicstaticintCompleteKnapsack2(int[]w,int[]v,intn,intm){int[][]dp=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(w[i-1]>j)dp[i][j]=dp[i-1][j];elsedp[i][j]=Math.max(dp[i-1][j],dp[i][j-w[i-1]]+v[i-1]);}}returndp[n][m];}2.3改进2:空间优化观察完全背包问题的方程: 可以看到,求解dp[i][j]时,其实只需要第i-1行的第j列或者当前第i行已经求过的第j-w[i]列的结果,其他行的结果是不需要的。 $$dp[j]=\begin{cases}dp[j],&w[i]>j\\max\{dp[j],dp[j-w[i]]+v[i]\},&w[i]≤j\end{cases}$$ 与0/1背包问题的空间优化不同,由于我们需要的第i行的第j-w[i]列在当前值j的左侧,因此我们必须对j从左向右遍历才能取到该值。 因此,空间优化后的完全背包问题的代码如下: 我们知道,动态规划是一个将大问题划分为小问题进行解决,从而一步步获取最优解的过程。 我们将F[i][j]表示为“将前i个物品放入容量为j的背包中的最大价值”,对于第i种物品,有两种情况: 怎么样?是不是更好理解了呢? 你有一个背包,最多能容纳的重量是m。现在有n种物品,每种物品有任意多个,第i个物品的重量为w[i],价值为v[i]。若背包恰好装满,求至多能装多大价值的物品?如果无解请返回0。 importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[]v=newint[n];int[]w=newint[n];for(inti=0;i 我们先观察完全背包问题的方程: 那么,多重背包与完全背包的区别在哪里呢?多重背包仅仅是对物品的数量多了个限制k≤c[i]: $$dp[i][j]=\begin{cases}dp[i-1][j],&w[i]>j\\max\{dp[i-1][j],max\{k*v[i]+dp[i-1][j-k*w[i]]\}\},&w[i]≤k*w[i]≤j&and&k≤c[i]\end{cases}$$ 所以,仅仅需要对k循环的条件作修改即可。代码如下: publicstaticintMultipleKnapsack1(int[]w,int[]v,int[]c,intn,intm){int[][]dp=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(w[i-1]>j)dp[i][j]=dp[i-1][j];else{inttemp=0;for(intk=1;k<=j/w[i-1]&&k<=c[i-1];k++){//对比完全背包,仅需修改此处temp=Math.max(temp,k*v[i-1]+dp[i-1][j-k*w[i-1]]);}dp[i][j]=Math.max(dp[i-1][j],temp);}}}returndp[n][m];}3.2改进1:空间优化同样的,多重背包问题可以进行空间优化,其思路与0/1背包问题一致,需要考虑到:若从左向右遍历,会导致后修改的右边的值需要用到先修改的左边的值。 因此,多重背包问题的j值需要从右向左遍历: publicstaticintMultipleKnapsack2(int[]w,int[]v,int[]c,intn,intm){int[]dp2=newint[m+1];for(inti=1;i<=n;i++){for(intj=m;j>=1;j--){if(w[i-1]<=j){for(intk=1;k<=j/w[i-1]&&k<=c[i-1];k++){dp2[j]=Math.max(dp2[j],k*v[i-1]+dp2[j-k*w[i-1]]);}}}}returndp[m];}3.3改进2:二进制优化、单调队列优化多重背包问题还可以进行二进制优化、单调队列优化。但笔者才疏学浅,就不多作介绍了。