1. 项目概述从“暴力枚举”到“优雅递推”刚接触算法那会儿一看到“背包问题”这四个字就头疼。不就是往一个容量有限的背包里塞东西让总价值最大吗听起来多简单。但真让你写代码第一反应往往是穷举所有物品的组合然后挨个算重量和价值。物品少还行一旦超过20个组合数爆炸程序跑一天都出不来结果。这就是典型的“暴力枚举”思维也是很多新手包括当年的我会掉进去的第一个坑。后来才知道这类“给定约束求最优”的问题有个专门的武器叫动态规划。它不像穷举那样蛮干而是把大问题拆成小问题记住小问题的答案避免重复计算最终像搭积木一样构建出大问题的解。背包问题尤其是经典的“0-1背包”几乎是所有动态规划入门教程的“第一课”。它结构清晰状态定义直观是理解动态规划“状态”和“转移”这两个核心概念的绝佳模型。这篇文章我就结合自己这些年刷题、面试和带新人的经验把背包问题掰开揉碎了讲清楚。我们不只讲最基础的0-1背包还会延伸到完全背包、多重背包这些变种并且每一部分都配上可以直接运行、逐行注释的C代码。我的目标是让你读完不仅能看懂原理更能自己动手写出来真正理解动态规划那种“用空间换时间”的优雅。2. 动态规划与背包问题核心思想拆解2.1 动态规划的本质记忆化与最优子结构动态规划听起来高大上其实核心思想就两点记忆化和最优子结构。我更喜欢用“查字典”和“搭积木”来比喻。想象一下你要计算斐波那契数列的第100项。如果傻傻地用递归f(n) f(n-1) f(n-2)你会重复计算无数次f(3),f(4)这样的中间结果。这就是重复子问题。动态规划的做法是开一个数组或者叫“字典”把算过的f(i)都存起来。下次再需要f(3)的时候不用重新算直接去数组里查。这个“存起来”的过程就是记忆化。那最优子结构呢意思是大问题的最优解可以由小问题的最优解推导出来。背包问题完美符合这个性质考虑前i个物品、背包容量为j时的最大价值肯定和考虑前i-1个物品、容量为j或者j - weight[i]时的最大价值有关。大问题前i个物品的解依赖于小问题前i-1个物品的解。这就为我们“搭积木”提供了可能先解决最小的子问题一个物品都不考虑或者背包容量为0然后一步步推导出最终答案。2.2 背包问题的分类与建模关键背包问题家族很庞大但面试和笔试中最常考的就是下面三种它们的区别主要在于每件物品能拿几次0-1背包每件物品最多拿一件要么0要么1。这是最基础、最重要的模型。完全背包每件物品可以拿无限件。多重背包每件物品有具体的数量限制比如最多拿s[i]件。无论哪种背包我们都需要明确几个关键要素这也是建模的第一步背包容量 (V)通常用一个整数表示比如背包最大能装10公斤。物品集合每个物品有两个关键属性体积 (weight[i])或重量占用背包的容量。价值 (value[i])物品的价值。目标在不超过背包容量的前提下选择物品使得装入背包的物品总价值最大。建模的过程就是定义“状态”和“状态转移方程”。状态就是我们“字典”里要存的东西在背包问题里最经典的状态定义是dp[i][j]表示考虑前i个物品在背包容量为j的情况下可以获取的最大价值。注意这里的“考虑前i个物品”并不意味着前i个物品都装进去了而是我们在做决策时面对的是前i个物品这个集合。这是理解状态定义的关键。3. 0-1背包问题从二维到一维的优化之旅3.1 二维DP最直观的理解方式我们先从最经典的二维动态规划数组开始。定义dp[i][j]为从下标为[0, i]的物品里任意取放进容量为j的背包所能达到的最大价值。那么对于每个物品i体积w[i], 价值v[i]在容量j下我们只有两种选择不放入物品 i那么最大价值就是考虑前i-1个物品、容量为j时的最大价值即dp[i-1][j]。放入物品 i首先背包容量j必须大于等于物品体积w[i]。放入后背包剩余容量为j - w[i]对应的最大价值是dp[i-1][j - w[i]]。再加上物品i本身的价值v[i]总价值为dp[i-1][j - w[i]] v[i]。我们的目标是价值最大所以在这两种选择中取最大值状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])(当j w[i]时) 如果j w[i]物品根本放不进去那么dp[i][j] dp[i-1][j]。初始化也很重要当背包容量j为0时什么都装不下dp[i][0] 0。当物品数量为0即不考虑任何物品时无论容量多大价值都是0dp[0][j] 0。下面是用C实现的二维DP解法#include iostream #include vector using namespace std; int knapsack_2d(vectorint weight, vectorint value, int capacity) { int n weight.size(); // 物品个数 // dp数组初始化为0vector容器会自动初始化但这里为了清晰我们明确一下维度 vectorvectorint dp(n, vectorint(capacity 1, 0)); // 初始化第一行即只考虑第一个物品 for (int j weight[0]; j capacity; j) { dp[0][j] value[0]; } // 遍历物品 for (int i 1; i n; i) { // 遍历背包容量 for (int j 0; j capacity; j) { if (j weight[i]) { // 当前背包容量装不下物品i dp[i][j] dp[i-1][j]; } else { // 装得下取“不装”和“装”的最大值 dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i]] value[i]); } } } return dp[n-1][capacity]; } int main() { vectorint weight {1, 3, 4}; vectorint value {15, 20, 30}; int capacity 4; int maxValue knapsack_2d(weight, value, capacity); cout 最大价值为: maxValue endl; // 输出35 (物品0和物品2) return 0; }3.2 一维DP滚动数组极致的空间优化仔细观察二维的状态转移方程dp[i][j]只依赖于dp[i-1][j]和dp[i-1][j - w[i]]。也就是说当前第i层的状态只和上一层i-1的状态有关。那我们是不是可以只用一个一维数组dp[j]来表示“容量为j的背包所能装下的最大价值”呢可以但这里有一个至关重要的细节遍历背包容量j的顺序必须是从大到小逆序。我们定义一维数组dp[j]容量为j的背包所背的物品最大价值为dp[j]。状态转移方程变为dp[j] max(dp[j], dp[j - weight[i]] value[i])。为什么需要逆序从capacity遍历到weight[i]我们来模拟一下。 假设物品i的重量weight[i] 1, 价值value[i] 15背包总容量capacity 4。 如果正序遍历j(从1到4)j1:dp[1] max(dp[1], dp[0] 15) 15。 (此时dp[0]0)j2:dp[2] max(dp[2], dp[1] 15) max(0, 1515)30。 发现问题了吗在计算dp[2]时用到的dp[1]已经是本轮更新过的值15而不是上一轮的值0。这相当于把物品i放了两次这违背了0-1背包“每个物品只能用一次”的规则。如果逆序遍历j(从4到1)j4:dp[4] max(dp[4], dp[3] 15)。此时dp[3]还是上一轮的值没问题。j3:dp[3] max(dp[3], dp[2] 15)。dp[2]也是上一轮的值。... 逆序保证了在计算dp[j]时dp[j - weight[i]]保存的是上一轮即考虑前i-1个物品时的状态从而保证了每个物品只被计算一次。一维DP的C实现如下代码更简洁空间复杂度从 O(n*capacity) 降到了 O(capacity)int knapsack_1d(vectorint weight, vectorint value, int capacity) { int n weight.size(); // 一维dp数组初始化为0 vectorint dp(capacity 1, 0); // 先遍历物品 for (int i 0; i n; i) { // 再逆序遍历背包容量 // 注意这里j的起始点是capacity终止点是weight[i] // 因为当j weight[i]时物品放不进去dp[j]保持不变无需操作 for (int j capacity; j weight[i]; --j) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } // 可以在这里打印每一轮后的dp数组观察状态变化 // for (int k 0; k capacity; k) cout dp[k] ; // cout endl; } return dp[capacity]; }实操心得一维DP的写法是面试中的常考点和优选写法。务必牢记“先遍历物品再逆序遍历背包容量”这个固定模式并理解其背后的原因。在纸上画一个简单的例子比如两个物品容量为4分别用正序和逆序模拟一遍dp数组的变化这个知识点就再也忘不掉了。4. 完全背包问题顺序遍历的奥秘完全背包和0-1背包的唯一区别就是每种物品有无限件。这一个小小的变化却让遍历顺序发生了根本性的改变。4.1 状态转移与遍历顺序分析在完全背包中对于物品i在背包容量j足够的情况下我们可以选择放0件、1件、2件...直到放不下为止。 理论上状态转移方程可以写成dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i], dp[i-1][j - 2*w[i]] 2*v[i], ...)但这需要多层循环效率不高。我们依然可以优化到一维数组。关键点来了在一维DP中完全背包的背包容量需要正序遍历。为什么回顾一下0-1背包逆序的原因是为了保证每个物品只被加入一次。而完全背包恰恰需要物品可以被加入多次。正序遍历j时在计算较大的dp[j]时较小的dp[j - weight[i]]可能已经在本轮被更新过即已经考虑过放入当前物品i这就相当于物品i被多次加入了。状态转移方程一维dp[j] max(dp[j], dp[j - weight[i]] value[i])(公式和0-1背包一样)遍历顺序先遍历物品再正序遍历背包容量。或者先正序遍历背包容量再遍历物品。这两种顺序在完全背包中都是可以的但通常我们使用第一种逻辑更清晰。4.2 代码实现与对比int complete_knapsack(vectorint weight, vectorint value, int capacity) { int n weight.size(); vectorint dp(capacity 1, 0); // 先遍历物品 for (int i 0; i n; i) { // 再正序遍历背包容量 for (int j weight[i]; j capacity; j) { // 注意这里是正序 dp[j] max(dp[j], dp[j - weight[i]] value[i]); } } return dp[capacity]; } int main() { vectorint weight {1, 3, 4}; vectorint value {15, 20, 30}; int capacity 4; cout 0-1背包最大价值: knapsack_1d(weight, value, capacity) endl; // 输出 35 cout 完全背包最大价值: complete_knapsack(weight, value, capacity) endl; // 输出 60 (装4个物品0) return 0; }可以看到同样的物品和容量完全背包能获得更高的价值60因为它可以重复选取价值15的物品0装满4的容量。注意事项完全背包和0-1背包的一维DP代码差异仅仅在于内层循环遍历背包容量的顺序。“逆序是0-1背包正序是完全背包”这句话请刻在脑子里。这是区分两者的核心代码特征。5. 多重背包问题化为0-1背包的经典思路多重背包是更一般的情况第i种物品最多有s[i]件。最直观的思路是把它转化为0-1背包问题把第i种物品看成是s[i]个独立的、体积和价值相同的物品然后用0-1背包的方法求解。这种方法被称为“二进制拆分优化”它比单纯拆成s[i]个物品要高效得多。5.1 二进制拆分优化原理假设某物品A有7件。如果拆成7个独立的A我们需要在0-1背包中考虑7次。二进制拆分的妙处在于我们可以用几个数的组合来表示出0~7之间的任意一个数。 7的二进制是111我们可以拆成1、2、4这三个数。它们可以组合成0 (不选)123 (12)45 (14)6 (24)7 (124)这样我们就把7个物品转化成了3个“新的虚拟物品”它们的体积和价值分别是原物品的1倍、2倍、4倍。在0-1背包中处理这3个虚拟物品就等价于处理原来最多选7次的情况但物品数量从7降到了3效率提升显著。对于任意数量s我们都可以将其拆分为1, 2, 4, ..., 2^(k-1), s - (2^k -1)这样一系列数其中2^k -1是小于等于s的最大二进制幂和。5.2 代码实现与示例int multiple_knapsack(vectorint weight, vectorint value, vectorint nums, int capacity) { // 第一步二进制拆分构建新的物品列表 vectorint new_weight, new_value; int n weight.size(); for (int i 0; i n; i) { int num nums[i]; // 物品i的数量 // 二进制拆分 for (int k 1; k num; k * 2) { new_weight.push_back(k * weight[i]); new_value.push_back(k * value[i]); num - k; } // 拆剩下的部分 if (num 0) { new_weight.push_back(num * weight[i]); new_value.push_back(num * value[i]); } } // 第二步对新的物品列表进行0-1背包求解使用一维DP vectorint dp(capacity 1, 0); int m new_weight.size(); // 新物品的个数 for (int i 0; i m; i) { for (int j capacity; j new_weight[i]; --j) { // 逆序遍历 dp[j] max(dp[j], dp[j - new_weight[i]] new_value[i]); } } return dp[capacity]; } int main() { // 物品重量价值数量 vectorint weight {1, 3, 4}; vectorint value {15, 20, 30}; vectorint nums {2, 1, 3}; // 物品0有2件物品1有1件物品2有3件 int capacity 9; int maxValue multiple_knapsack(weight, value, nums, capacity); cout 多重背包最大价值: maxValue endl; // 可以手动推算最优解可能是 2个物品0(30) 1个物品1(20) 1个物品2(30) 80重量1*2349 return 0; }6. 常见问题与排查技巧实录在实际编码和解题中会遇到一些典型的“坑”。这里我总结几个最常见的问题和排查思路。6.1 dp数组初始化陷阱问题dp数组应该初始化为0吗对于纯价值最大化的背包问题通常是的。但有一类变种问题例如“恰好装满背包的最大价值”初始化就不同了。普通问题dp[j]表示容量为j的背包最多能装多少价值。初始化dp[0]0其他也为0。因为任何容量的背包不装物品价值就是0。恰好装满dp[j]表示容量为j的背包恰好装满时的最大价值。初始化dp[0]0但其他dp[j]要初始化为一个“非法值”比如INT_MIN求最大价值时或INT_MAX求最小物品数时。因为容量为j的背包在没有任何方案能恰好装满时它的价值应该是“未定义”的我们用负无穷来表示这种状态在状态转移时只有从有效的状态非负无穷才能转移过来。// 恰好装满背包的最大价值 int knapsack_exact(vectorint weight, vectorint value, int capacity) { vectorint dp(capacity 1, INT_MIN); // 初始化为负无穷 dp[0] 0; // 容量为0的背包装满的价值就是0 for (int i 0; i weight.size(); i) { for (int j capacity; j weight[i]; --j) { if (dp[j - weight[i]] ! INT_MIN) { // 只有前一个状态是有效的才能转移 dp[j] max(dp[j], dp[j - weight[i]] value[i]); } } } // 如果 dp[capacity] 还是 INT_MIN说明没有恰好装满的方案 return dp[capacity] INT_MIN ? -1 : dp[capacity]; }6.2 遍历顺序引发的逻辑错误这是最常出错的地方务必形成条件反射求组合数顺序无关 vs 求排列数顺序有关如果先遍历物品再遍历背包容量求的是组合数。因为物品的顺序被固定了。例如{1,5}和{5,1}被视为同一种组合。如果先遍历背包容量再遍历物品求的是排列数。因为对于每个容量我们都可以重新考虑所有物品{1,5}和{5,1}会被算作两种不同的排列。经典例题零钱兑换II求凑成总金额的硬币组合数需要先遍历物品硬币再遍历背包金额。而爬楼梯问题求到楼顶的方法数每次可以走1或2步本质上是一个完全背包求排列数的问题需要先遍历背包楼梯阶数再遍历物品步数1或2。// 组合数零钱兑换II int change(int amount, vectorint coins) { vectorint dp(amount 1, 0); dp[0] 1; // 金额为0的组合数为1什么都不选 for (int coin : coins) { // 先遍历物品硬币 for (int j coin; j amount; j) { // 再正序遍历背包金额 dp[j] dp[j - coin]; } } return dp[amount]; } // 排列数爬楼梯进阶版每次可以爬[1,m]阶 int climbStairs(int n, int m) { vectorint dp(n 1, 0); dp[0] 1; for (int j 0; j n; j) { // 先遍历背包楼梯阶数 for (int i 1; i m; i) { // 再遍历物品步数 if (j i) dp[j] dp[j - i]; } } return dp[n]; }6.3 复杂问题如何识别为背包问题很多问题披着“应用题”的外衣核心却是背包。识别关键词“容量/限制”总重量不超过W总时间不超过T总金额不超过Amount。“物品”每个物品有“消耗”体积/重量/成本和“收益”价值/重要性。“最优”求最大价值、最小成本、最多数量等。转化步骤明确什么是“背包容量”限制条件。明确什么是“物品”以及它的“重量”和“价值”。明确是0-1背包每个物品最多选一次、完全背包物品无限还是多重背包物品有限次。套用对应的模板。举例分割等和子集问题。问题给定一个只包含正整数的非空数组判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 转化背包容量V 数组总和sum的一半。物品 数组中的每个数字。物品重量 数字值物品价值 数字值这里价值和重量相同。每个数字只能选一次是0-1背包。问题转化为是否存在一种选择使得物品总重量恰好等于V即“恰好装满”的0-1背包可行性问题。 代码核心就是0-1背包的一维DPdp[j]表示容量为j的背包是否能被恰好装满。bool canPartition(vectorint nums) { int sum accumulate(nums.begin(), nums.end(), 0); if (sum % 2 ! 0) return false; // 总和为奇数不可能平分 int target sum / 2; vectorbool dp(target 1, false); dp[0] true; // 容量为0的背包总是可以装满不选任何物品 for (int num : nums) { // 遍历物品 for (int j target; j num; --j) { // 逆序遍历背包容量 if (dp[j - num]) dp[j] true; // 如果 j-num 能被装满那么加上当前物品 numj 也能被装满 } if (dp[target]) return true; // 提前结束 } return dp[target]; }动态规划的精髓在于多练、多总结。背包问题作为DP的入门基石其思想会贯穿许多更复杂的问题。最好的学习方式就是找一些经典的力扣题目比如“416. 分割等和子集”、“474. 一和零”、“518. 零钱兑换 II”、“377. 组合总和 Ⅳ”自己动手实现一遍并思考它们分别对应哪种背包模型遍历顺序又是怎样的。当你能够不假思索地写出这些题目的状态定义和转移方程时你对背包问题的理解就真正到位了。
1. 项目概述从“暴力枚举”到“优雅递推”刚接触算法那会儿一看到“背包问题”这四个字就头疼。不就是往一个容量有限的背包里塞东西让总价值最大吗听起来多简单。但真让你写代码第一反应往往是穷举所有物品的组合然后挨个算重量和价值。物品少还行一旦超过20个组合数爆炸程序跑一天都出不来结果。这就是典型的“暴力枚举”思维也是很多新手包括当年的我会掉进去的第一个坑。后来才知道这类“给定约束求最优”的问题有个专门的武器叫动态规划。它不像穷举那样蛮干而是把大问题拆成小问题记住小问题的答案避免重复计算最终像搭积木一样构建出大问题的解。背包问题尤其是经典的“0-1背包”几乎是所有动态规划入门教程的“第一课”。它结构清晰状态定义直观是理解动态规划“状态”和“转移”这两个核心概念的绝佳模型。这篇文章我就结合自己这些年刷题、面试和带新人的经验把背包问题掰开揉碎了讲清楚。我们不只讲最基础的0-1背包还会延伸到完全背包、多重背包这些变种并且每一部分都配上可以直接运行、逐行注释的C代码。我的目标是让你读完不仅能看懂原理更能自己动手写出来真正理解动态规划那种“用空间换时间”的优雅。2. 动态规划与背包问题核心思想拆解2.1 动态规划的本质记忆化与最优子结构动态规划听起来高大上其实核心思想就两点记忆化和最优子结构。我更喜欢用“查字典”和“搭积木”来比喻。想象一下你要计算斐波那契数列的第100项。如果傻傻地用递归f(n) f(n-1) f(n-2)你会重复计算无数次f(3),f(4)这样的中间结果。这就是重复子问题。动态规划的做法是开一个数组或者叫“字典”把算过的f(i)都存起来。下次再需要f(3)的时候不用重新算直接去数组里查。这个“存起来”的过程就是记忆化。那最优子结构呢意思是大问题的最优解可以由小问题的最优解推导出来。背包问题完美符合这个性质考虑前i个物品、背包容量为j时的最大价值肯定和考虑前i-1个物品、容量为j或者j - weight[i]时的最大价值有关。大问题前i个物品的解依赖于小问题前i-1个物品的解。这就为我们“搭积木”提供了可能先解决最小的子问题一个物品都不考虑或者背包容量为0然后一步步推导出最终答案。2.2 背包问题的分类与建模关键背包问题家族很庞大但面试和笔试中最常考的就是下面三种它们的区别主要在于每件物品能拿几次0-1背包每件物品最多拿一件要么0要么1。这是最基础、最重要的模型。完全背包每件物品可以拿无限件。多重背包每件物品有具体的数量限制比如最多拿s[i]件。无论哪种背包我们都需要明确几个关键要素这也是建模的第一步背包容量 (V)通常用一个整数表示比如背包最大能装10公斤。物品集合每个物品有两个关键属性体积 (weight[i])或重量占用背包的容量。价值 (value[i])物品的价值。目标在不超过背包容量的前提下选择物品使得装入背包的物品总价值最大。建模的过程就是定义“状态”和“状态转移方程”。状态就是我们“字典”里要存的东西在背包问题里最经典的状态定义是dp[i][j]表示考虑前i个物品在背包容量为j的情况下可以获取的最大价值。注意这里的“考虑前i个物品”并不意味着前i个物品都装进去了而是我们在做决策时面对的是前i个物品这个集合。这是理解状态定义的关键。3. 0-1背包问题从二维到一维的优化之旅3.1 二维DP最直观的理解方式我们先从最经典的二维动态规划数组开始。定义dp[i][j]为从下标为[0, i]的物品里任意取放进容量为j的背包所能达到的最大价值。那么对于每个物品i体积w[i], 价值v[i]在容量j下我们只有两种选择不放入物品 i那么最大价值就是考虑前i-1个物品、容量为j时的最大价值即dp[i-1][j]。放入物品 i首先背包容量j必须大于等于物品体积w[i]。放入后背包剩余容量为j - w[i]对应的最大价值是dp[i-1][j - w[i]]。再加上物品i本身的价值v[i]总价值为dp[i-1][j - w[i]] v[i]。我们的目标是价值最大所以在这两种选择中取最大值状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])(当j w[i]时) 如果j w[i]物品根本放不进去那么dp[i][j] dp[i-1][j]。初始化也很重要当背包容量j为0时什么都装不下dp[i][0] 0。当物品数量为0即不考虑任何物品时无论容量多大价值都是0dp[0][j] 0。下面是用C实现的二维DP解法#include iostream #include vector using namespace std; int knapsack_2d(vectorint weight, vectorint value, int capacity) { int n weight.size(); // 物品个数 // dp数组初始化为0vector容器会自动初始化但这里为了清晰我们明确一下维度 vectorvectorint dp(n, vectorint(capacity 1, 0)); // 初始化第一行即只考虑第一个物品 for (int j weight[0]; j capacity; j) { dp[0][j] value[0]; } // 遍历物品 for (int i 1; i n; i) { // 遍历背包容量 for (int j 0; j capacity; j) { if (j weight[i]) { // 当前背包容量装不下物品i dp[i][j] dp[i-1][j]; } else { // 装得下取“不装”和“装”的最大值 dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i]] value[i]); } } } return dp[n-1][capacity]; } int main() { vectorint weight {1, 3, 4}; vectorint value {15, 20, 30}; int capacity 4; int maxValue knapsack_2d(weight, value, capacity); cout 最大价值为: maxValue endl; // 输出35 (物品0和物品2) return 0; }3.2 一维DP滚动数组极致的空间优化仔细观察二维的状态转移方程dp[i][j]只依赖于dp[i-1][j]和dp[i-1][j - w[i]]。也就是说当前第i层的状态只和上一层i-1的状态有关。那我们是不是可以只用一个一维数组dp[j]来表示“容量为j的背包所能装下的最大价值”呢可以但这里有一个至关重要的细节遍历背包容量j的顺序必须是从大到小逆序。我们定义一维数组dp[j]容量为j的背包所背的物品最大价值为dp[j]。状态转移方程变为dp[j] max(dp[j], dp[j - weight[i]] value[i])。为什么需要逆序从capacity遍历到weight[i]我们来模拟一下。 假设物品i的重量weight[i] 1, 价值value[i] 15背包总容量capacity 4。 如果正序遍历j(从1到4)j1:dp[1] max(dp[1], dp[0] 15) 15。 (此时dp[0]0)j2:dp[2] max(dp[2], dp[1] 15) max(0, 1515)30。 发现问题了吗在计算dp[2]时用到的dp[1]已经是本轮更新过的值15而不是上一轮的值0。这相当于把物品i放了两次这违背了0-1背包“每个物品只能用一次”的规则。如果逆序遍历j(从4到1)j4:dp[4] max(dp[4], dp[3] 15)。此时dp[3]还是上一轮的值没问题。j3:dp[3] max(dp[3], dp[2] 15)。dp[2]也是上一轮的值。... 逆序保证了在计算dp[j]时dp[j - weight[i]]保存的是上一轮即考虑前i-1个物品时的状态从而保证了每个物品只被计算一次。一维DP的C实现如下代码更简洁空间复杂度从 O(n*capacity) 降到了 O(capacity)int knapsack_1d(vectorint weight, vectorint value, int capacity) { int n weight.size(); // 一维dp数组初始化为0 vectorint dp(capacity 1, 0); // 先遍历物品 for (int i 0; i n; i) { // 再逆序遍历背包容量 // 注意这里j的起始点是capacity终止点是weight[i] // 因为当j weight[i]时物品放不进去dp[j]保持不变无需操作 for (int j capacity; j weight[i]; --j) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } // 可以在这里打印每一轮后的dp数组观察状态变化 // for (int k 0; k capacity; k) cout dp[k] ; // cout endl; } return dp[capacity]; }实操心得一维DP的写法是面试中的常考点和优选写法。务必牢记“先遍历物品再逆序遍历背包容量”这个固定模式并理解其背后的原因。在纸上画一个简单的例子比如两个物品容量为4分别用正序和逆序模拟一遍dp数组的变化这个知识点就再也忘不掉了。4. 完全背包问题顺序遍历的奥秘完全背包和0-1背包的唯一区别就是每种物品有无限件。这一个小小的变化却让遍历顺序发生了根本性的改变。4.1 状态转移与遍历顺序分析在完全背包中对于物品i在背包容量j足够的情况下我们可以选择放0件、1件、2件...直到放不下为止。 理论上状态转移方程可以写成dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i], dp[i-1][j - 2*w[i]] 2*v[i], ...)但这需要多层循环效率不高。我们依然可以优化到一维数组。关键点来了在一维DP中完全背包的背包容量需要正序遍历。为什么回顾一下0-1背包逆序的原因是为了保证每个物品只被加入一次。而完全背包恰恰需要物品可以被加入多次。正序遍历j时在计算较大的dp[j]时较小的dp[j - weight[i]]可能已经在本轮被更新过即已经考虑过放入当前物品i这就相当于物品i被多次加入了。状态转移方程一维dp[j] max(dp[j], dp[j - weight[i]] value[i])(公式和0-1背包一样)遍历顺序先遍历物品再正序遍历背包容量。或者先正序遍历背包容量再遍历物品。这两种顺序在完全背包中都是可以的但通常我们使用第一种逻辑更清晰。4.2 代码实现与对比int complete_knapsack(vectorint weight, vectorint value, int capacity) { int n weight.size(); vectorint dp(capacity 1, 0); // 先遍历物品 for (int i 0; i n; i) { // 再正序遍历背包容量 for (int j weight[i]; j capacity; j) { // 注意这里是正序 dp[j] max(dp[j], dp[j - weight[i]] value[i]); } } return dp[capacity]; } int main() { vectorint weight {1, 3, 4}; vectorint value {15, 20, 30}; int capacity 4; cout 0-1背包最大价值: knapsack_1d(weight, value, capacity) endl; // 输出 35 cout 完全背包最大价值: complete_knapsack(weight, value, capacity) endl; // 输出 60 (装4个物品0) return 0; }可以看到同样的物品和容量完全背包能获得更高的价值60因为它可以重复选取价值15的物品0装满4的容量。注意事项完全背包和0-1背包的一维DP代码差异仅仅在于内层循环遍历背包容量的顺序。“逆序是0-1背包正序是完全背包”这句话请刻在脑子里。这是区分两者的核心代码特征。5. 多重背包问题化为0-1背包的经典思路多重背包是更一般的情况第i种物品最多有s[i]件。最直观的思路是把它转化为0-1背包问题把第i种物品看成是s[i]个独立的、体积和价值相同的物品然后用0-1背包的方法求解。这种方法被称为“二进制拆分优化”它比单纯拆成s[i]个物品要高效得多。5.1 二进制拆分优化原理假设某物品A有7件。如果拆成7个独立的A我们需要在0-1背包中考虑7次。二进制拆分的妙处在于我们可以用几个数的组合来表示出0~7之间的任意一个数。 7的二进制是111我们可以拆成1、2、4这三个数。它们可以组合成0 (不选)123 (12)45 (14)6 (24)7 (124)这样我们就把7个物品转化成了3个“新的虚拟物品”它们的体积和价值分别是原物品的1倍、2倍、4倍。在0-1背包中处理这3个虚拟物品就等价于处理原来最多选7次的情况但物品数量从7降到了3效率提升显著。对于任意数量s我们都可以将其拆分为1, 2, 4, ..., 2^(k-1), s - (2^k -1)这样一系列数其中2^k -1是小于等于s的最大二进制幂和。5.2 代码实现与示例int multiple_knapsack(vectorint weight, vectorint value, vectorint nums, int capacity) { // 第一步二进制拆分构建新的物品列表 vectorint new_weight, new_value; int n weight.size(); for (int i 0; i n; i) { int num nums[i]; // 物品i的数量 // 二进制拆分 for (int k 1; k num; k * 2) { new_weight.push_back(k * weight[i]); new_value.push_back(k * value[i]); num - k; } // 拆剩下的部分 if (num 0) { new_weight.push_back(num * weight[i]); new_value.push_back(num * value[i]); } } // 第二步对新的物品列表进行0-1背包求解使用一维DP vectorint dp(capacity 1, 0); int m new_weight.size(); // 新物品的个数 for (int i 0; i m; i) { for (int j capacity; j new_weight[i]; --j) { // 逆序遍历 dp[j] max(dp[j], dp[j - new_weight[i]] new_value[i]); } } return dp[capacity]; } int main() { // 物品重量价值数量 vectorint weight {1, 3, 4}; vectorint value {15, 20, 30}; vectorint nums {2, 1, 3}; // 物品0有2件物品1有1件物品2有3件 int capacity 9; int maxValue multiple_knapsack(weight, value, nums, capacity); cout 多重背包最大价值: maxValue endl; // 可以手动推算最优解可能是 2个物品0(30) 1个物品1(20) 1个物品2(30) 80重量1*2349 return 0; }6. 常见问题与排查技巧实录在实际编码和解题中会遇到一些典型的“坑”。这里我总结几个最常见的问题和排查思路。6.1 dp数组初始化陷阱问题dp数组应该初始化为0吗对于纯价值最大化的背包问题通常是的。但有一类变种问题例如“恰好装满背包的最大价值”初始化就不同了。普通问题dp[j]表示容量为j的背包最多能装多少价值。初始化dp[0]0其他也为0。因为任何容量的背包不装物品价值就是0。恰好装满dp[j]表示容量为j的背包恰好装满时的最大价值。初始化dp[0]0但其他dp[j]要初始化为一个“非法值”比如INT_MIN求最大价值时或INT_MAX求最小物品数时。因为容量为j的背包在没有任何方案能恰好装满时它的价值应该是“未定义”的我们用负无穷来表示这种状态在状态转移时只有从有效的状态非负无穷才能转移过来。// 恰好装满背包的最大价值 int knapsack_exact(vectorint weight, vectorint value, int capacity) { vectorint dp(capacity 1, INT_MIN); // 初始化为负无穷 dp[0] 0; // 容量为0的背包装满的价值就是0 for (int i 0; i weight.size(); i) { for (int j capacity; j weight[i]; --j) { if (dp[j - weight[i]] ! INT_MIN) { // 只有前一个状态是有效的才能转移 dp[j] max(dp[j], dp[j - weight[i]] value[i]); } } } // 如果 dp[capacity] 还是 INT_MIN说明没有恰好装满的方案 return dp[capacity] INT_MIN ? -1 : dp[capacity]; }6.2 遍历顺序引发的逻辑错误这是最常出错的地方务必形成条件反射求组合数顺序无关 vs 求排列数顺序有关如果先遍历物品再遍历背包容量求的是组合数。因为物品的顺序被固定了。例如{1,5}和{5,1}被视为同一种组合。如果先遍历背包容量再遍历物品求的是排列数。因为对于每个容量我们都可以重新考虑所有物品{1,5}和{5,1}会被算作两种不同的排列。经典例题零钱兑换II求凑成总金额的硬币组合数需要先遍历物品硬币再遍历背包金额。而爬楼梯问题求到楼顶的方法数每次可以走1或2步本质上是一个完全背包求排列数的问题需要先遍历背包楼梯阶数再遍历物品步数1或2。// 组合数零钱兑换II int change(int amount, vectorint coins) { vectorint dp(amount 1, 0); dp[0] 1; // 金额为0的组合数为1什么都不选 for (int coin : coins) { // 先遍历物品硬币 for (int j coin; j amount; j) { // 再正序遍历背包金额 dp[j] dp[j - coin]; } } return dp[amount]; } // 排列数爬楼梯进阶版每次可以爬[1,m]阶 int climbStairs(int n, int m) { vectorint dp(n 1, 0); dp[0] 1; for (int j 0; j n; j) { // 先遍历背包楼梯阶数 for (int i 1; i m; i) { // 再遍历物品步数 if (j i) dp[j] dp[j - i]; } } return dp[n]; }6.3 复杂问题如何识别为背包问题很多问题披着“应用题”的外衣核心却是背包。识别关键词“容量/限制”总重量不超过W总时间不超过T总金额不超过Amount。“物品”每个物品有“消耗”体积/重量/成本和“收益”价值/重要性。“最优”求最大价值、最小成本、最多数量等。转化步骤明确什么是“背包容量”限制条件。明确什么是“物品”以及它的“重量”和“价值”。明确是0-1背包每个物品最多选一次、完全背包物品无限还是多重背包物品有限次。套用对应的模板。举例分割等和子集问题。问题给定一个只包含正整数的非空数组判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 转化背包容量V 数组总和sum的一半。物品 数组中的每个数字。物品重量 数字值物品价值 数字值这里价值和重量相同。每个数字只能选一次是0-1背包。问题转化为是否存在一种选择使得物品总重量恰好等于V即“恰好装满”的0-1背包可行性问题。 代码核心就是0-1背包的一维DPdp[j]表示容量为j的背包是否能被恰好装满。bool canPartition(vectorint nums) { int sum accumulate(nums.begin(), nums.end(), 0); if (sum % 2 ! 0) return false; // 总和为奇数不可能平分 int target sum / 2; vectorbool dp(target 1, false); dp[0] true; // 容量为0的背包总是可以装满不选任何物品 for (int num : nums) { // 遍历物品 for (int j target; j num; --j) { // 逆序遍历背包容量 if (dp[j - num]) dp[j] true; // 如果 j-num 能被装满那么加上当前物品 numj 也能被装满 } if (dp[target]) return true; // 提前结束 } return dp[target]; }动态规划的精髓在于多练、多总结。背包问题作为DP的入门基石其思想会贯穿许多更复杂的问题。最好的学习方式就是找一些经典的力扣题目比如“416. 分割等和子集”、“474. 一和零”、“518. 零钱兑换 II”、“377. 组合总和 Ⅳ”自己动手实现一遍并思考它们分别对应哪种背包模型遍历顺序又是怎样的。当你能够不假思索地写出这些题目的状态定义和转移方程时你对背包问题的理解就真正到位了。
