纯完全背包（题型1，3）考虑的是最大价值，所以不用管遍历顺序

求最小数（题型4）也不用管遍历顺序

01背包

• 二维初始化：j >= weight[0]时，dp[0][j] = value[0]，（题型1，3），dp[0][0]分情况讨论或dp[0][0] = 1，其余全0（题型2，参考目标和）

• 一维初始化：i >= weight[0]时，dp[i] = value[0]，（题型1，3），dp[0] = 1，（题型2）

• 二维遍历顺序：题型1，2，3先遍历物品还是先遍历背包都可以，第二层从小到大和从大大小都可以，因为由上方和左上方推出

• 一维遍历顺序：题型1，2，3先遍历物品再遍历背包，第二层从右到左遍历

完全背包

• 二维初始化：j >= weight[0]时，dp[0][j] = (j / weight(0)) * value[0]，（题型1，3）

• 一维初始化：i >= weight[0]时，dp[i] = (i / weight[0]) * value[0]，（题型1，3），dp[0] = 1，（题型2），dp[0] = 0，（题型4）

• 二维遍历顺序：仅考虑题型1，3，先遍历物品还是先遍历背包都可以，第二层从小到大和从大大小都可以

• 一维遍历顺序：题型2需考虑是组合还是排列问题，先遍历物品（组合），先遍历背包（排列），第二层从左到右遍历，题型1，3，4先遍历物品还是先遍历背包都可以，第二层从左到右遍历

题型

1、能否能装满背包、最多装多少（价值等于重量）

• LeetCode416：分割等和子集

• LeetCode1049：最后一块石头的重量Ⅱ

• dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

2、装满背包有几种方法

• LeetCode494：目标和

• LeetCode518：零钱兑换Ⅱ（完全背包，组合数）

• LeetCode377：组合总和Ⅳ（完全背包，排列数）

• 卡码网57：爬楼梯进阶版（完全背包，排列数）

• dp[j] += dp[j - nums[i]]

3、背包装满最大价值

• 卡码网46题

• 卡码网52题（完全背包）

• 完全：max(dp[i-1][j] , dp[i][j-weight[i]] + value[i])

• 01：max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i])

• dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

4、装满背包所有物品的最小个数

• LeetCode322：零钱兑换（完全背包，最小数）

• LeetCode279：完全平方数（完全背包，最小数）

• dp[j] = min(dp[j - coins[i]] + 1, dp[j])