前端算法--背包问题

背包问题

背包问题是一类经典的算法问题，属于动态规划解法范畴，其核心是在一个范围内择出最优解。

一般描述为：给定一组物品和一个背包，每种物品都有自己的重量和价格，在背包限定的总重量内，我们如何选择，才能使得物品的总价格最高。

非完全背包

如下面的背包基础问题：

描述

有若干个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值。

问最多能装入背包的总价值是多大?

样例

样例 1：

输入：

1
2
3

m = 10
A = [2, 3, 5, 7]
V = [1, 5, 2, 4]

输出：

解释：

装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9

样例 2：

输入：

1
2
3

m = 10
A = [2, 3, 8]
V = [2, 5, 8]

输出：

解释：

装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10

解法

我们有n种物品，物品j的重量为wj，价格为pj。

我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。

针对每个物品x，我们可以选择0个或者1个（用或者不用），转换成具体公式：

在总重量不超过W的前提下，我们希望总价格最高。对于Y ≤ W，我们将在总重量不超过Y的前提下，总价格所能达到的最高值定义为A(Y)。A(W)即为问题的答案。

显然，A(Y)满足：

其中，pj为第j种物品的价格。

对于第一种情况，如果总重量为0，总价值也为0。
对于第二种情况，总重量为Y时背包的最高价值可能有两种情况，第一种是该重量无法被完全填满，这对应于表达式A(Y - 1)。第二种是刚好填满，这对应于一个包含一系列刚好填满的可能性的集合，其中的可能性是指当最后放进包中的物品恰好是重量为wj的物品时背包填满并达到最高价值。而这时的背包价值等于重量为wj物品的价值pj和当没有放入该物品时背包的最高价值之和。故归纳为表达式pj + A(Y - wj)。最后把所有上述情况中背包价值的最大值求出就得到了A(Y)的值。

所以这里就存在了递推关系，依次计算A(0), A(1), …, A(W)，并把每一步骤的结果存入表中供后续步骤使用，完成这些步骤后A(W)即为最终结果，符合了动态规划思路，我们把这个思路转换为代码：

var backPack = function(m, A, V) {
  var dp = new Array(m + 1).fill(0) // 动态规划数组，初始化值为0，即没有任何物品，价值为0
  // 外层循环物品
  for (var i = 0; i < A.length; i++) {
    // 内层循环背包，倒序避免重复
    for (var j = m; j >= 0; j--) {
      if (j - A[i] >= 0) {
        // dp[j]表示公式里面的A(Y),V[i]表示pj,A[i]表示wj
        dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i])
      }
    }
  }
  return dp[m] // 达到背包容量时，即最大价值
}

这样，就得到了答案，这个问题中，每个物品只能被使用一次，即不能重复使用，对于可以重复使用的物品，我们称之为完全背包问题。

完全背包

描述

给定若干种物品, 每种物品都有无限个. 第 i 个物品的体积为 A[i], 价值为 V[i].

再给定一个容量为 m 的背包. 问可以装入背包的最大价值是多少?

样例

样例 1:

1
2
3

输入: A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 10
输出: 15
解释: 装入三个物品 1 (A[1] = 3, V[1] = 5), 总价值 15.

样例 2:

1
2
3

输入: A = [1, 2, 3], V = [1, 2, 3], m = 5
输出: 5
解释: 策略不唯一. 比如, 装入五个物品 0 (A[0] = 1, V[0] = 1).

解法

我们直接给出代码：

var backPack = function(m, A, V) {
  var dp = new Array(m + 1).fill(0) // 动态规划数组，初始化值为0，即没有任何物品，价值为0
  // 外层循环背包
  for (var i = 0; i <= m; i++) {
    // 内层循环物品
    for (var j = 0; j < A.length; j++) {
      if (i - A[j] >= 0) {
        dp[i] = Math.max(dp[i], dp[i - A[j]] + V[j])
      }
    }
  }
  return dp[m] // 达到背包容量时，即最大价值
}

和上面非完全背包区别是，由于物品可以无限次使用，我们把物品循环放在了内部，外层循环背包。

背包问题模板

万能模板

上面的解法，采用了数学公式的思路，推断出动态规划的递推公式，这显然很复杂，但是看最终的代码实现，我们发现这类背包问题一般是如下步骤：

首先定义一个DP数组，保存每一步递推的值。
两层循环，外层物品或内层背包。
判断临界条件，应用递推公式计算。
通过DP数组，得出最终结果。

结合上面的步骤，以及完全背包和非完全背包的区别，我们可以得到解决背包问题或者类似背包问题的通用模板万能公式，如下：

target：背包
nums：物品
var dp = new Array(target + 1).fill(0);
dp[0] = 1;// 根据实际情况是否设置初始值
for(var i = 1; i <= target; i++){
  for(var j = 0; j < nums.length; j++){
    ...公式
  }
}

非完全背包：每个物品只能用一次（内层循环倒序）。
完全背包：每个物品可以重复使用（内层循环正序）。
非完全背包：
- 外层for循环遍历物品，内层for遍历背包。
完全背包：
- 如果求组合数（不考虑结果元素的顺序）就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数（考虑顺序）就是外层for遍历背包，内层for循环遍历物品。

真题套用

结合leetcode上的原题，我们可以把背包问题大致分为以下几类：

1、组合问题：

494.目标和

518.零钱兑换 II

组合问题公式：dp[i] += dp[i-num]
2、排列问题

377.组合总和 Ⅳ

排列问题公式：dp[i] += dp[i-num]
3、True、False问题：

139.单词拆分（组合）

416.分割等和子集（组合）

True、False问题公式：dp[i] = dp[i] or dp[i-num]
4、最大最小问题：

474.一和零

322.零钱兑换（组合）

279.完全平方数

最大最小问题公式：dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)

下面，结合几个典型真题例子，来看看如何套用公式。

322.零钱兑换：

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1 2	输入：coins = [2], amount = 3 输出：-1

示例 3：

1 2	输入：coins = [1], amount = 0 输出：0

示例 4：

1 2	输入：coins = [1], amount = 1 输出：1

示例 5：

1 2	输入：coins = [1], amount = 2 输出：2

解法

金额可以抽象为背包，硬币可以抽象为物品，这就转换成了一个背包问题，题目中描述硬币数量无限使用，那么就是一个完全背包问题，那么就可以套用模板：

只求数量，不考虑顺序，符合组合数，外层for物品，内层for背包。
最小值问题，使用最小值公式。
完全背包问题，内层循环正序。

得到代码如下所示：

var coinChange = function(coins, amount) {
  var dp = new Array(amount + 1).fill(Number.MAX_SAFE_INTEGER) dp[0] = 0
  for (var i = 0; i < coins.length; i++) {
    for (var j = 0; j <= amount; j++) {
      if (j >= coins[i]) {
        dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1) // 最小值问题公式
      }
    }
  }
  return dp[amount] == Number.MAX_SAFE_INTEGER ? -1 : dp[amount]
};

518.零钱兑换II：

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

1
2
3

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

1 2	输入：amount = 10, coins = [10] 输出：1

解法

只求数量，不考虑顺序，符合组合数，外层for物品，内层for背包。
组合问题，使用组合公式。
完全背包问题，内层循环正序。

得到代码如下所示：

var change = function(amount, coins) {
  var dp = new Array(amount + 1).fill(0)
  // 总数为0时，只有一种方案兑换 就是所有硬币都不选择
  dp[0] = 1
  for (var i = 0; i < coins.length; i++) {
    for (var j = 0; j <= amount; j++) {
      if (j - coins[i] >= 0) {
        dp[j] = dp[j] + dp[j - coins[i]] // 组合问题公式
      }
    }
  }
  return dp[amount]
};

139.单词拆分：

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

1
2
3

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1 2	输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

解法

字符串s可以抽象为背包，单词列表wordDict可以抽象为物品，这就转换成了一个背包问题，题目中描述可以使用重复的单词，那么就是一个完全背包问题，那么就可以套用模板：

单词顺序影响结果，符合排列数，外层for背包，内层for物品。
True，False问题，使用True，False公式。
完全背包问题，内层循环正序。

得到代码如下所示：

var wordBreak = function(s, wordDict) {
  var dp = new Array(s.length + 1).fill(false)
  // dp[i] 表示以 i 结尾的字符串是否可以被 wordDict 中组合而成
  dp[0] = true // 空字符可以不从wordDict中选择，也能组成
  for (var i = 1; i <= s.length; i++) {
    for (var j = 0; j < wordDict.length; j++) {
      var s1 = wordDict[j] // s1表示当前的字符串
      // temp表示字符串s中截取s1长度的临时串
      var temp = s.substr(i - s1.length, s1.length)
      // 临时串和当前s1相等时，可匹配
      if (temp == s1) {
        dp[i] = dp[i] || dp[i - s1.length]
      }
    }
  }
  return dp[s.length]
}

其他相关的公式，也都可以套用，这里就不在赘述。掌握了背包问题公式，大部分的问题都可以迎刃而解了！

吕小鸣前端博客

热爱前端，关注前端开发技术

前端算法--背包问题

背包问题

非完全背包

完全背包

背包问题模板

万能模板

真题套用