完全背包问题：零钱兑换

目录

题目

image.png|560

题解：背包问题的变种

有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

每个物品的数量是无限，所以叫做 **完全背包问题

三、明确状态与选择

状态

  • 背包的剩余容量，即还能装多少重量的物件
  • 可选择的物品

选择

  • 选择放入背包
  • 选择不放入背包

明确 dp 数组的定义

dp[i][w] 的定义如下：

背包变种的解释：

  • 若只使用前 i 个物品（可以重复使用），当背包剩余容量为w 时，有 dp[i][w] 种方法可以装满背包 回到原题：
  • 若只使用 coins 中的前 i 个（i 从 1 开始计数）硬币的面值，若想凑出金额 w，有 dp[i][w] 种凑法

根据 动态规划套路框架 写出伪码

base case

// 面值为 0，什么不用做，就是一种凑法
dp[...][0] = 1;

// 不使用任何硬币面值，凑法为 0 
dp[0][...] = 0;

根据 框架 写出 伪码

① 初始化 dp 数组
dp = [][]

  
② base case
dp[0][..] = 0
dp[..][0] = 1

③ 根据状态，嵌套遍历
for i in [1..N]:
    for j in [1..amount]:
        选择 1：
            把物品 i 装进背包,
        选择 2：
            不把物品 i 装进背包
④ 返回 dp
return dp[N][amount]

根据 选择 写出 状态转移方程

  • 如果你不把这第 i 个物品装入背包，也就是说你不使用 coins[i-1] 这个面值的硬币
    • 那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。
  • 如果你把这第 i 个物品装入了背包，也就是说你使用 coins[i-1] 这个面值的硬币，
    • 那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。

最终代码

var change = function (amount, coins) {
  var n = coins.length;
  // 初始化 dp 及base case
  var dp = [];
  for (var i = 0; i <= n; i++) {
    dp[i] = [];
    for (var w = 0; w <= amount; w++) {
      // 面值为 0，什么不用做，就是一种凑法
      if (w === 0) {
        dp[i][w] = 1;
      } else {
        dp[i][w] = 0;
      }
    }
  }
  // 状态决定 for 循环嵌套层数
  for (var i = 1; i <= n; i++) {
    for (var w = 1; w <= amount; w++) {
      // 如果 w - coins[i - 1] >= 0，说明可以选择当前硬币
      if (w - coins[i - 1] >= 0) {
        // 选择当前硬币和不选择当前硬币两种选择
        dp[i][w] =
          dp[i - 1][w] + // 不选择当前硬币
          dp[i][w - coins[i - 1]]; // 选择当前硬币
      } else {
        // 如果 w - coins[i - 1] < 0，说明当前硬币无法选择
        // 因为当前硬币面值比 w 大，根本凑不出 w
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][amount];
};