背包问题总复习（纯理论）

二刷一遍《代录》的动规问题，突然发现好像没那么晦涩难懂了，特此来梳理一下使用动规的一些思路，以及背包问题的解题步骤。以防下一次忘记~

首先，动规解决的问题：重复子问题

其次，动规题型：一般动规问题与背包问题

再者，两类题型的差异：一般动规问题与背包问题差异在于遍历，一般动规问题只需要一次遍历即可，背包问题需要两层遍历：背包与物品。

对于背包问题：分为01背包、完全背包、多重背包

01背包：该题的关键在于，物品不能重复利用，只能使用1次。

动规五步中，有两种遍历方法：

一种  先遍历物品 再遍历背包

一种  先遍历背包 再遍历物品

在遍历背包时，如果使用二维dp，任意写法都可，无限制。

如果使用一维滚动数组，则必须先物品后背包，且保证背包的遍历顺序是  倒序遍历！！！防止前面背包中的数被后面计算来的覆盖。

完全背包：该题的关键在于，物品可以无限制取用。

动规五步中，遍历方式与是否是排列还是组合有关！！！！

装满背包：

当求组合数，即答案与排列顺序无关时，需要外层遍历物品，内层遍历背包；

当求排列数，即答案与排列顺序有关时，需要外层遍历背包，内层遍历物品；

最大最小：

求最大最小时，两种遍历方法都可以。

在遍历背包时，一维dp中，需要保证背包是正序遍历！

多重背包问题：问题关键在于，同一个物品的个数不唯1，可以选择有限个。

多重背包的解题思路：将其转换为01背包问题，即将不唯一的物品拆解成1个1个即可。

动规五步中，一维滚动数组，必须背包倒序遍历！！

ps：

1. 解题时，弄懂背包是什么，物品是什么；

2. 解题时，弄懂dp的含义；

3.解题时，弄懂背包问题是  求最大最小值 还是 求 装满问题

装满：dp[j]+=dp[j-nums[i]];

最大最小：dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);