描述

动态规划-子集背包问题 - 图1case

  • input
    • [1, 5, 11, 5]
  • output
    • True. s1 = {1, 5, 5} s2 = {11}

递归解法

思路：

  • 元素要么选， 要么不选. 假设存在s1集合， 那么S种元素要么在集合s1种，要么不在 ```python def backtrack(nums: [int], i: int, target: int) -> bool:

    base case

    if i == len(nums):
    1.   if target == 0:
    2.       return True
    3.   return False
    else: # 要么选择要么不选择
    1.   return backtrack(nums, i + 1, target) or backtrack(nums, i + 1, target - nums[i])

if name == ‘main‘: nums = [1, 2, 3, 4, 5] print(backtrack(nums, 0, sum(nums) / 2))

  1. <a name="q5JX4"></a>
  2. ## 动态规划解法
  4. - `dp[i][j]`  物品：[1-i]，任选（0、1），是否刚好能填满背包容量j， 注意 `basecase` 
  5. - 状态转移方程![](https://cdn.nlark.com/yuque/__latex/396c96fe993b8ca3d02d636be15d3f8f.svg#card=math&code=dp%5Bi%5D%5Bj%5D%3D%0A%5Cbegin%7Bcases%7D%0Adp%5Bi-1%5D%5Bj%5D%20%5C%20or%20%5C%20%20dp%5Bi-1%5D%5Bj-num_i%5D%26%20%5Ctext%7Bnum_i%20%3C%3D%20j%2C%20%E9%80%89%28%E5%8F%AA%E8%83%BD%E9%80%89%E4%B8%80%E6%AC%A1%29%E4%B8%8E%E4%B8%8D%E9%80%89%7D%5C%5C%0Adp%5Bi%20-%201%5D%5Bj%5D%26%20%5Ctext%7Bnum_i%20%3E%20j%2C%20%E4%B8%8D%E8%83%BD%E9%80%89%7D%5C%5C%0A%0A%5Cend%7Bcases%7D&height=54&id=oUyC5)
  6. ```python
  7. def sub_package(nums, W):
  8.     def func(x: []):
  10.     # dp[i][j]: 物品：[1-i]，任选（0、1），是否刚好能填满背包容量j
  11.     # dp数组初始化，basecase
  12.     dp = [[False for j in range(W + 1)] for i in range(len(nums) + 1)]
  13.     for row in range(len(nums) + 1):
  14.         dp[row][0] = True
  16.     for i in range(1, len(nums) + 1):  # 物品
  17.         for j in range(1, W + 1):  #
  18.             if nums[i - 1] <= j:  #
  19.                 dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
  20.             else:
  21.                 dp[i][j] = dp[i - 1][j]
  23.     for row in dp:
  24.         print(row)
  27. if __name__ == '__main__':
  28.     nums = [1, 2, 3, 6]
  29.     sub_package(nums, 6)