背包问题模板

如何在一个背包容量为 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: