如何在一个背包容量为 i 的背包中装入最大质量或者转入组合.<br />
<br />背包问题五步曲:<br />
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例来推导dp数组
<br />遍历顺序:<br />
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
<br />背包问题技巧：<br />
- 如果是0-1背包，即数组中的元素不可重复使用，物品放在外循环，背包容量在内循环，且内循环倒序；
for num in nums:
for i in range(target, nums-1, -1):
- 如果是完全背包，即数组中的元素可重复使用，物品放在外循环，背包容量在内循环。且内循环正序。
for num in nums:
for i in range(nums, target+1):
- 如果组合问题需考虑元素之间的顺序，需将背包容量放在外循环，将物品放在内循环。
for i in range(1, target+1):
for num in nums:
网友评论