描述

给定整数组nums, 整数W, 求nums有几种方案可以凑成W。数据可以使用多次

递归解法：

  • 元素选择：选可以选择1词或者多次 ```python def backtrack(w: [], W: int, i: int) -> int:

    base case

    if i == len(w) or W == 0:

    1.   if W == 0:
    2.       return 1
    3.   return 0
  1. else:
  2.     if w[i] <= W:
  4.         return sum(
  5.             (backtrack(w, W - w[i], i),  # 选了这次，下次可能继续选， 至少选一次
  6.              backtrack(w, W, i + 1)))  # 可以选但不选。 一次都不选
  8.     else: 
  9.         return backtrack(w, W, i + 1)  # 没法选

if name == ‘main‘: coins = [1, 2, 5] print(backtrack(coins, 4, 0))

  1. <a name="ksKrK"></a>
  2. ### 动态规划解法
  4. - `dp[i][j] = x` :![](https://cdn.nlark.com/yuque/__latex/0c2080d99cd8af3d3a77e4c909e981b3.svg#card=math&code=%E7%BB%99%E5%AE%9A%E6%95%B0%E5%AD%97J%EF%BC%8Cnum_1...num_i%E4%B8%80%E5%85%B1%E6%9C%89X%E7%A7%8D%E5%87%91%E5%87%BAj%E7%9A%84%E6%96%B9%E6%B3%95&height=24&width=356)
  5. - 状态转移：![](https://cdn.nlark.com/yuque/__latex/e7cad25f3138abe4bfd7441a0bc18f0f.svg#card=math&code=dp%5Bi%5D%5Bj%5D%3D%0A%5Cbegin%7Bcases%7D%0Adp%5Bi%5D%5Bj-num_i%5D%20%2B%20dp%5Bi-1%5D%5Bj%5D%26%20%5Ctext%7Bnums%20%3C%3D%20j%2C%20%E9%80%89%28%E5%8F%AF%E5%A4%9A%E9%80%89%29%E4%B8%8E%E4%B8%8D%E9%80%89%7D%5C%5C%0Adp%5Bi%20-%201%5D%5Bj%5D%26%20%5Ctext%7Bnums%20%3E%20j%2C%20%E4%B8%8D%E8%83%BD%E9%80%89%7D%5C%5C%0A%0A%5Cend%7Bcases%7D&height=54&width=526)
  6. ```python
  7. def full_package(nums, W):
  8.     # dp数组初始化，
  9.     dp = [[0 for j in range(W + 1)] for i in range(len(nums) + 1)]
  10.     for row in range(len(nums) + 1):  # 重量为0时， 唯一方案就是不用选择任何数，
  11.         dp[row][0] = 1
  12.     for i in range(1, len(nums) + 1):  # 物品
  13.         for j in range(1, W + 1):  #
  14.             if nums[i - 1] <= j:  #
  15.                 dp[i][j] = dp[i][j - nums[i - 1]] + dp[i - 1][j]
  16.             else:
  17.                 dp[i][j] = dp[i - 1][j]
  19.     for row in dp:
  20.         print(row)
  23. if __name__ == '__main__':
  24.     coins = [1, 2, 5]
  25.     full_package(coins, 5)

总结

  • 元素可多选的处理
  • 状态转移和自顶向下的关联
  • 有时候， 数组有序性会将重复情况排除