总结背包问题
背包问题总结篇
0/1背包
01背包是物品只能使用一次，存在放或者不放两种情况
对于01背包问题：
- 二维的dp数组：遍历的前后顺序和物品容量层次顺序都可以交换顺序。因为二维保留了很多上下文信息能够推出结果 （这里将物品和容量分别看作一维，容量本身可能是多维的也笼统看作一维
- 一维的dp数组（滚动数组）：只能是先遍历物品，再遍历容量，而且内层容量的遍历只能是倒序的。因为只能放入一次，如果先遍历容量再遍历物品的话每一个dp**[i]**都只会放进一个物品，即背包里只有一个能装入的最大价值物品
完全背包
完全背包是物品可以无限次使用
一维的dp数组：对于容量的遍历应该是顺序进行的，因为完全背包物品可以多次放入，而纯完全背包问题对于是先遍历容量还是先遍历物品都是可以的，因为纯完全背包问题求的是能否装满背包，但对于一些非纯完全背包问题，先后顺序会影响结果是组合数还是排列数
如果是求装满背包有多少种方式，递推公式都是一样的，关键在于遍历顺序
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
完全背包的三类问题：
- 求组合数
- 求排列数
- 求最小数
多重背包
有N种物品和一个容量为V的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci，价值是Wi 。 求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
解决的办法就是将有限个物品全部分开作为单独一个物品，这样就转换为了01背包问题，按01背包问题的解法就行
递推公式
能否装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
装满背包有几种方法：dp[j] += dp[j - nums[i]]
背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])
- 零钱兑换
- 完全平方数
遍历顺序
01背包
- 二维dp数组01背包先遍历物品还是先遍历容量都可以，且第二层for循环是从小到大遍历
- 一维dp数组01背包只能先遍历物品再遍历容量，而且容量是倒序遍历
完全背包
- 纯完全背包问题是求是否能够装满，所以先遍历物品或先遍历背包都可以，第二层for循环从小到大
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品
- 如果是求最小数那么先后顺序都可以