[Vssue]背包总结篇.md

[youngyangyang04]

https://www.programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html

[Du1in9]

递推公式

👉 问能否装满背包（或者最多装多少）：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], dp[j - coins[i]] + 1)

遍历顺序

👉 01 背包 二维 dp 数组：先遍历物品或背包皆可，且第二层是从小到大遍历。 一维 dp 数组：先遍历物品再遍历背包，且第二层是从大到小遍历。

👉 完全背包（一维 dp 数组） 求组合数：先遍历物品再遍历背包，且第二层是从小到大遍历。 求排列数：先遍历背包再遍历物品，且第二层是从小到大遍历。 求最小值：先遍历物品或背包皆可，且第二层是从小到大遍历。