01背包问题总结

最近刷leetcode过程中遇到了很多背包问题，趁此机会总结下如何用动态规划解决背包问题及其各种变体。

写在前面：

本文适合有一定dp基础的读者阅读，用来复习回顾背包相关问题，遇到类似问题可快速秒掉。

基础描述：

给定一个容量大小为W的背包，和一系列物品，物品有价值和获取代价。

问题分类：

• 0/1背包问题

  416. 分割等和子集：物品有限，能否装满

  494. 目标和：转换后变成，物品有限，能否装满

  1049. 最后一块石头的重量 II：其实和416分割等和子集一样，只不过比较难看出来

• 完全背包问题

  322. 零钱兑换：装满的同时，物品数量最少

  518. 零钱兑换 II：装满组合数（注意不是排列数，2/2/1等价于2/1/2）

  377. 组合总和 Ⅳ：装满排列数

  70. 爬楼梯：装满排列数

  746. 使用最小花费爬楼梯：装满，代价最小

  面试题 08.01. 三步问题：装满排列数

  983. 最低票价：和零钱兑换类似

  279. 完全平方数：装满，数量最少

• 多重背包问题

  leetcode上暂时没有遇到！

• 分组背包问题

  1155. 掷骰子的N种方法：每种物品数量若干个，装满方案数

• 二维费用背包

  474. 一和零：两种费用，背包最多装多少

问法分类：

• 最大价值：不超过背包容量或获取代价，获取物品的最大价值。
• 最小代价：装满背包，代价最小
• 最小数量：装满背包，物品数量最少
• 能否装满：物品没有价值属性，重量即为代价，能否装满背包。
• 装满方案数：物品有各自重量，把背包装满的方案数。这种问法还有两个细分情景：
  • 排列数：1,2,3和1,3,2属于同一种方案。
  • 组合数：1,2,3和1,3,2属于不同种方案。

算法模板：

不同问法的模板基本一样，这里以“最大价值”问法为例，总结各种类型问题的模板。其他问法模板类似，只不过需要把max改成min或者计数或者boolean的与、或之类的。

• 0/1背包问题：指物品数量有限，有N件物品，容量为V的背包。

  • 思路： $dp[i][v]$ 表示从前i件物品中取出重量为v的物品的最大价值，那么我们$dp[N] [V]$就是我们最终要的答案。

  • 状态转移方程：对于第i件物品，我们可以要，也可以不要：

    • 要第i件物品：那么$dp[i][v]= dp[i-1][v-w[i]]+val[i]$
    • 不要第i件物品：那么$dp[i][v]= dp[i-1][v]$

    我们两者取其大，则得到$dp[i] [v] = max\{dp[i-1] [v], dp[i-1] [v-w[i]]+val[i]\}$。

  • 代码模板

    从前面状态转移方程来看需要建立一个二维数组，但是利用滚动数组（因为更新$dp[i] [*]$的时候，只用到了$dp[i-1] [*]$的值），一维数组即可解决该问题：

    1 2 3 4 5 6 7 8

    int[] dp = new int[V+1]; for(int i = 0; i < N; ++i){ //为什么从后往前？因为dp[i][v]计算过程中用到了dp[i-1][v-w[i]] //v-w[i]一定小于v，从后往前保证用到的dp[v-w[i]]属于上一层的 for(int v = V; v-w[i] >= 0; --v){ dp[v] = Math.max(dp[v], dp[v-w[i]]+val[i]); } }

• 完全背包问题：指物品数量无限，有N种物品，可任意取用，容量为V的背包。

  • 思路：在0/1背包中，因为物品数量有限，我们是从物品角度分析的，即：对于某一件物品要或者不要，它对某一容量背包的影响。但是在完全背包中物品数量无限，我们就需要从背包容量角度分析。其实就是dp的第一个维度由物品转变成背包容量。

  • 状态转移方程：这里我的思路和很多博客上给的不太一样，我们用一维dp来搞定完全背包问题。

    现在这样思考：假设背包容量为v时，在某个方案下，获得物品的价值最高。这个方案的最后一步拿到的物品k，那么是不是应当有$dp[v]=max\{dp[v-w[k]], 0<k<N且v-w[k]>=0\}$。

  • 代码模板

    1 2 3 4 5 6 7 8 9

    int[] dp = new int[V+1]; for(int v = 1; v <= V; ++v){ //遍历所有物品种类 for(int i = 0； i < N; ++i){ if(v - w[i] >= 0){ dp[v] = Math.max(dp[v], dp[v-w[i]]+val[i]); } } }

• 多重背包问题：所谓多重背包就是：一共有N种物品，每个物品有n[i]件。

  这各问题和0/1背包的解法也是基本一样。有两种方案：

  • 方案1：把物品展开，这样一共有n[0]件物品0，n[1]件物品1，以此类推，这样就完全转换成0/1背包问题了
  • 方案2：在0/1背包的两重循环之间加一重循环，这样第一重循环表示物品种类，第二重循环表示每种物品的数量，第三种循环表示背包容量。

  对于这两种方案的状态转移方程和代码模板，本文不作过多叙述了。

• 分组背包问题：有N件物品，和一个容量为V的背包。这些物品被分成若干组，每组中物品只能选一个，求最大价值。可参考1155. 掷骰子的N种方法。

  • 思路：这种类型问题，可以顺着0/1背包的思路来，把每一组当做0/1背包中的一件物品。在0/1背包中，我们直接拿物品来更新状态，现在由于“物品”是一组物品，因此需要在循环最内部加一重循环，遍历这个组中所有物品。

  • 状态转移方程：$dp[i] [v] = max\{dp[i-1] [v], dp[i-1] [v-w[k]]+val[i]\ |\ 物品k属于第i组\}$

  • 代码模板：和0/1背包一样，只不过最内层加一重遍历分组的循环。

    1 2 3 4 5 6 7 8 9 10 11

    int[] dp = new int[V+1]; //N表示分组数量 for(int i = 0; i < N; ++i){ //为什么从后往前？因为dp[i][v]计算过程中用到了dp[i-1][v-w[i]] //v-w[i]一定小于v，从后往前保证用到的dp[v-w[i]]属于上一层的 for(int v = V; v-w[i] >= 0; --v){ //遍历分组i for(int k = 0; k < K; ++k) dp[v] = Math.max(dp[v], dp[v-w[k]]+val[k]); } }

• 二维费用背包：每个物品的有两种代价，两种代价都不能超过背包允许的总代价，求可获取物品的最大价值。可参考这一题474. 一和零。这里以0/1背包为例，完全背包解法类似。

  • 思路：这个解法也很简单，原来一种代价用一维dp，现在两种代价，改成二维dp即可$dp[v][u]$表示代价为v和u时获取物品的最大价值。

  • 状态转移方程：$dp[v][u]=max\{dp[v][u], dp[v-w_v{i}][u-w_u{i}]+val[i]\}$。

  • 代码模板：加一重U的for循环即可。