一、先理解问题什么是背包问题想象一个场景你去露营带了一个背包背包最多能装 5公斤 的东西。现在有 3 件物品帐篷3公斤价值 4 元假设是租的价格睡袋2公斤价值 3 元食物4公斤价值 5 元问题你该怎么选让总价值最大但不超过 5 公斤这就是01背包问题0和1表示要么拿要么不拿不能拿一半。最笨的方法暴力枚举把所有组合都试一遍。选法 总重量 总价值 可行什么都不拿 0 0 ✓只拿帐篷 3 4 ✓只拿睡袋 2 3 ✓只拿食物 4 5 ✓帐篷睡袋 5 7 ✓帐篷食物 7 9 ✗超重睡袋食物 6 8 ✗超重全拿 9 12 ✗超重最好的选法帐篷 睡袋 总价值 7如果物品很多比如 100 件2¹⁰⁰ 种组合电脑也算不出来。所以需要动态规划来聪明地计算。1、01背包每个物品只能选一次这是最基础的背包类型其他背包都可以看作它的变体。场景有N个物品每个物品只有一个选或不选。背包容量为M每个物品有体积v[i]和价值w[i]求最大价值。核心思想用dp[j]表示容量为j的背包能装的最大价值。考虑第i个物品时只有两种选择不选dp[j]保持不变继承前i-1个物品的结果选dp[j] dp[j - v[i]] w[i]腾出空间装它状态转移方程dp[j] max(dp[j], dp[j - v[i]] w[i])关键细节——为什么容量要逆序遍历因为每个物品只能取一次逆序保证dp[j - v[i]]还是前i-1个物品的状态而不是已经拿过第i个物品的状态。如果正序可能会出现一个物品被重复使用多次的情况。// 01背包核心代码for (int i 1; i N; i) {for (int j M; j v[i]; j–) { // 逆序dp[j] max(dp[j], dp[j - v[i]] w[i]);}}完全背包每个物品无限供应场景每个物品有无限个可以随便取。核心变化既然物品可以无限取dp[j - v[i]]应该允许已经拿过第i个物品所以容量正序遍历。// 完全背包核心代码for (int i 1; i N; i) {for (int j v[i]; j M; j) { // 正序dp[j] max(dp[j], dp[j - v[i]] w[i]);}}直观理解01背包倒序是怕自己拿自己完全背包正序是允许反复拿自己。