背包问题模板

背包问题模板

Tans 935 2022-03-21

如何在一个背包容量为 i 的背包中装入最大质量或者转入组合.


背包问题五步曲:

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例来推导dp数组


遍历顺序:

  1. 如果求组合数就是外层for循环遍历物品,内层for遍历背包
  2. 如果求排列数就是外层for遍历背包,内层for循环遍历物品


背包问题技巧:

  1. 如果是0-1背包,即数组中的元素不可重复使用,物品放在外循环,背包容量在内循环,且内循环倒序;
for num in nums:
    for i in range(target, nums-1, -1):
  1. 如果是完全背包,即数组中的元素可重复使用,物品放在外循环,背包容量在内循环。且内循环正序。
for num in nums:
    for i in range(nums, target+1):
  1. 如果组合问题需考虑元素之间的顺序,需将背包容量放在外循环,将物品放在内循环
for i in range(1, target+1):
    for num in nums: