背包问题是动态规划算法中非常经典的一类问题，也是笔试面试中常见的一类问题。
背包问题有四类：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：二进制优化、单调队列优化多重背包问题还可以进行二进制优化、单调队列优化。但笔者才疏学浅，就不多作介绍了。