1. 项目概述从“装包”到“最优解”的经典博弈如果你写过C/C并且对算法稍微有点兴趣那“0-1背包问题”这个名字你肯定不陌生。它就像一个算法领域的“Hello World”但又远比“Hello World”复杂和深刻。简单来说它描述了一个非常现实的场景你有一个容量有限的背包面前摆着一堆物品每个物品有自己的重量和价值。你的目标很简单——在不超过背包容量的前提下选出一些物品装进去使得背包里所有物品的总价值最大。这里的“0-1”意味着每个物品只有两种命运要么整个装进去1要么完全不装0不能只装一部分。这个看似简单的模型却构成了无数现实问题的抽象核心从资源分配、投资组合优化到项目排期、网络带宽切割背后都有它的影子。我之所以想详细聊聊这个算法是因为我发现很多初学者甚至一些有经验的开发者对它的理解往往停留在“背下动态规划的状态转移方程”这个层面。网上能找到的源码也常常是干巴巴的几行核心循环缺少对为什么这么设计、边界条件怎么处理、空间如何优化以及如何从结果反推具体方案这些关键细节的剖析。这就像只给了你一张藏宝图却没告诉你怎么看懂地图上的符号和比例尺。这篇内容我会结合我这些年刷题、面试和实际项目中的经验把0-1背包算法的里里外外、前前后后都拆解清楚并附上可以直接编译运行的、注释详尽的C/C源码。无论你是正在准备算法面试还是想在项目中应用优化思想相信都能从这里找到你需要的东西。2. 核心思路拆解暴力、记忆化与动态规划的演进之路理解一个算法最好的方式就是看它如何从最笨的方法一步步优化而来。0-1背包问题也不例外这个演进过程本身就充满了算法设计的智慧。2.1 暴力枚举法最直观的起点最直接的想法就是既然每个物品要么选要么不选那么对于n个物品总共就有2的n次方种可能的组合。我们遍历所有这些组合检查每种组合的总重量是否超过背包容量如果没有就计算其总价值并记录下最大值。这种方法绝对正确因为穷举了所有可能性。用C实现可以利用递归或者位运算来枚举子集。// 暴力递归枚举指数时间复杂度 O(2^n) #include iostream #include vector #include algorithm using namespace std; struct Item { int weight; int value; }; int knapsackBruteForce(int capacity, const vectorItem items, int index) { // 递归基没有物品可选或背包容量为负无效状态 if (index 0 || capacity 0) { return 0; } // 情况1不选择当前物品 int profitWithout knapsackBruteForce(capacity, items, index - 1); // 情况2选择当前物品前提是能装下 int profitWith 0; if (items[index].weight capacity) { profitWith items[index].value knapsackBruteForce(capacity - items[index].weight, items, index - 1); } // 返回两种情况下的最大值 return max(profitWith, profitWithout); }注意这个递归函数存在大量的重复计算。例如考虑前i个物品、剩余容量为c的状态可能会在不同的递归路径中被计算无数次。当n超过20时运行时间将变得不可接受。但它为我们理解问题结构奠定了基础每个物品是一个决策点决策会产生两个分支。2.2 记忆化搜索递归备忘录消除重复子问题我们注意到在递归树中很多状态由当前考虑的物品索引i和剩余背包容量c共同定义被重复计算了。记忆化搜索的核心思想就是“用空间换时间”开辟一个二维数组memo[i][c]用来记录“从前i个物品中做选择背包剩余容量为c时能获得的最大价值”这个子问题的结果。如果这个状态之前计算过就直接查表返回避免重复递归。// 记忆化搜索自顶向下 int knapsackMemo(int capacity, const vectorItem items, int index, vectorvectorint memo) { if (index 0 || capacity 0) { return 0; } // 如果这个状态已经计算过直接返回结果 if (memo[index][capacity] ! -1) { return memo[index][capacity]; } // 不选当前物品 int profitWithout knapsackMemo(capacity, items, index - 1, memo); int profitWith 0; // 选当前物品 if (items[index].weight capacity) { profitWith items[index].value knapsackMemo(capacity - items[index].weight, items, index - 1, memo); } // 将计算结果存入备忘录再返回 memo[index][capacity] max(profitWith, profitWithout); return memo[index][capacity]; } // 初始化备忘录并调用 int solveWithMemo(int capacity, const vectorItem items) { int n items.size(); // 备忘录初始化为-1表示未计算 vectorvectorint memo(n, vectorint(capacity 1, -1)); return knapsackMemo(capacity, items, n - 1, memo); }实操心得记忆化搜索是连接递归思维和动态规划思维的桥梁。它的代码结构和暴力递归几乎一样只是多了一个“记事本”。在面试或竞赛中如果你先写出记忆化搜索面试官通常会认为你对问题有深刻理解。初始化备忘录时容量维度要开到capacity1因为剩余容量可能是0到capacity之间的任何整数。2.3 动态规划DP自底向上的递推美学记忆化搜索是“自顶向下”的我们是从最终目标考虑所有n个物品容量为C开始递归地分解成子问题。动态规划则反其道而行之采用“自底向上”的填表法。我们定义dp[i][c]为只考虑前i个物品物品编号0到i-1在背包容量为c时能获得的最大价值。注意这里i表示“考虑前几个”而不是“第几个物品的索引”这一定义在编码时更清晰。那么状态如何转移呢对于第i个物品在0-indexed中实际是items[i-1]我们有两种选择不装它那么最大价值就是在前i-1个物品里、容量为c时的最大价值即dp[i-1][c]。装它前提是它的重量w[i-1] c。如果装那么背包需要先为它腾出w[i-1]的空间剩下的c - w[i-1]的容量用来装前i-1个物品。所以总价值是v[i-1] dp[i-1][c - w[i-1]]。我们要的是最大价值所以取这两种选择中的最大值dp[i][c] max(dp[i-1][c], v[i-1] dp[i-1][c - w[i-1]]) 其中第二个选项仅在c w[i-1]时有效。初始化当物品数量为0i0时无论容量多大最大价值都是0。当背包容量为0c0时无论有多少物品最大价值也都是0因为什么都装不下。所以dp[0][...] 0且dp[...][0] 0。// 经典二维DP解法 int knapsackDP(int capacity, const vectorint weights, const vectorint values) { int n weights.size(); // dp数组大小 (n1) x (capacity1)多出来的一行一列用于初始化 vectorvectorint dp(n 1, vectorint(capacity 1, 0)); // 开始填表i从1到nc从1到capacity for (int i 1; i n; i) { int w weights[i - 1], v values[i - 1]; // 当前物品的重量和价值 for (int c 1; c capacity; c) { // 默认选择不装当前物品 dp[i][c] dp[i - 1][c]; // 如果当前背包容量能装下这个物品考虑装它的可能性 if (c w) { dp[i][c] max(dp[i][c], v dp[i - 1][c - w]); } } } // 最终答案考虑所有n个物品容量为capacity return dp[n][capacity]; }这个二维DP表就是我们理解0-1背包问题最核心的蓝图。它的时间复杂度是O(n * capacity)空间复杂度也是O(n * capacity)。对于大多数笔试面试场景这个解法已经足够。但追求极致的我们肯定不会止步于此。3. 空间优化从二维表格到一维滚动的艺术仔细观察状态转移方程dp[i][c]只依赖于dp[i-1][c]和dp[i-1][c - w]。也就是说当前行i的数据只和上一行i-1的数据有关。那我们何必保存整个n行的表格呢我们完全可以只用一个一维数组dp[c]来表示“在当前考虑的物品范围内容量为c时的最大价值”。但这里有一个至关重要的细节如果我们从左到右遍历容量c那么在计算dp[c]时dp[c - w]可能已经被当前这轮循环更新过了这就变成了“完全背包”问题的逻辑一个物品可以选多次而不是0-1背包每个物品只能选一次。因为dp[c - w]如果被更新意味着我们可能已经装入了当前这个物品现在又试图再装一次。解决方案是从右向左遍历容量c。这样当我们计算dp[c]时dp[c - w]对应的还是上一轮即考虑前i-1个物品时的结果保证了每个物品只被考虑一次。// 空间优化的一维DP解法滚动数组 int knapsackDPOptimized(int capacity, const vectorint weights, const vectorint values) { int n weights.size(); // dp[c] 表示容量为c的背包能获得的最大价值 vectorint dp(capacity 1, 0); // 遍历每个物品 for (int i 0; i n; i) { int w weights[i], v values[i]; // 关键内层循环倒序遍历容量 for (int c capacity; c w; --c) { // 状态转移max(不选i, 选i) dp[c] max(dp[c], v dp[c - w]); } // 当 c w 时dp[c]保持不变等于上一轮的值 } return dp[capacity]; }注意事项这是0-1背包最核心、最常用的代码模板务必深刻理解并熟记。内层循环的c w条件可以整合到循环条件c capacity; c w; --c中这样代码更简洁也避免了内部的if判断。这个模板的时间复杂度依然是O(n * capacity)但空间复杂度降到了O(capacity)。4. 重构具体方案如何知道到底选了哪些物品DP算法只告诉了我们最大价值是多少但老板可能还想知道“具体是哪些宝贝让我赚了这么多”这就需要我们根据填好的DP表来回溯重构出选择的方案。回溯的思路是“逆推决策”。我们从最终状态dp[n][capacity]开始如果用的是一维数组则需要额外记录信息或再算一次二维表看这个价值是怎么来的。如果dp[i][c] dp[i-1][c]说明第i个物品实际索引i-1没有被选中最大价值完全来自于前i-1个物品。否则如果dp[i][c] values[i-1] dp[i-1][c - weights[i-1]]说明第i个物品被选中了。那么我们就将它加入结果列表然后将状态回溯到i-1和c - weights[i-1]继续判断。// 基于二维DP表回溯具体方案 vectorint getSelectedItems(int capacity, const vectorint weights, const vectorint values, const vectorvectorint dp) { int n weights.size(); vectorint selected; int c capacity; // 从最后一个物品开始向前回溯 for (int i n; i 0 c 0; --i) { // 如果当前值不等于上一行同容量的值说明当前物品被选中了 // 注意由于浮点数精度问题实际中比较整数这里用不等于判断是安全的 if (dp[i][c] ! dp[i-1][c]) { // 选中了第i-1个物品因为dp的i对应前i个物品 selected.push_back(i - 1); // 背包剩余容量减少 c - weights[i - 1]; } // 如果相等则物品i-1未被选中i--c不变继续循环 } // 因为我们是从后往前找的所以得到的物品索引顺序是逆序的可以reverse一下不过通常不影响 // reverse(selected.begin(), selected.end()); return selected; } // 使用示例 void solveAndTrack() { vectorint weights {2, 3, 4, 5}; vectorint values {3, 4, 5, 6}; int capacity 8; int n weights.size(); // 1. 计算二维DP表 vectorvectorint dp(n 1, vectorint(capacity 1, 0)); for (int i 1; i n; i) { for (int c 1; c capacity; c) { dp[i][c] dp[i-1][c]; if (c weights[i-1]) { dp[i][c] max(dp[i][c], values[i-1] dp[i-1][c - weights[i-1]]); } } } cout 最大价值: dp[n][capacity] endl; // 2. 回溯方案 vectorint selected getSelectedItems(capacity, weights, values, dp); cout 选中的物品索引: ; for (int idx : selected) cout idx ; cout endl; cout 对应重量和价值: ; for (int idx : selected) cout ( weights[idx] , values[idx] ) ; cout endl; }实操心得如果空间优化后只用了一维数组又想回溯方案一个常见的做法是在填一维DP表的同时用一个额外的二维布尔数组choice[i][c]来记录在状态(i, c)下是否选择了物品i。这会增加O(n*capacity)的空间但有时是值得的。另一种更省空间但费点时间的方法是先得到最大价值maxVal然后重新跑一遍DP过程模拟决策路径。5. 边界处理与常见陷阱实录理论很完美但一写代码就报错下面这些坑我几乎每个都踩过。5.1 容量与重量为0的情况如果背包容量为0那么最大价值肯定是0无论有什么物品。如果某个物品的重量为0但价值为正那它无论如何都应该被选中因为它“白送”价值。我们的DP代码能正确处理吗在二维DP初始化时dp[...][0] 0所以容量为0的列都是0没问题。对于重量为0的物品在一维DP的倒序循环for (int c capacity; c w; --c)中因为w0循环条件c 0对于c从capacity到0都成立。这时dp[c] max(dp[c], v dp[c - 0]) max(dp[c], v dp[c])。如果v 0那么dp[c]会不断被更新为v dp[c]这会导致价值无限增加吗会的这是一个逻辑漏洞。实际上重量为0的物品可以无限拿但0-1背包每个物品只能拿一个。所以我们需要特殊处理如果w0那么这个物品肯定选直接给所有dp[c]加上v即可。在实际问题中重量为0的物品很少见但意识到这个边界很重要。5.2 重量和价值的数据类型题目给的重量和价值一定是整数吗不一定。有时可能是浮点数。DP数组的下标是背包容量如果容量和重量是浮点数就不能直接用作数组索引。常见的处理方法是放大取整如果小数位数固定如最多两位小数可以将所有重量和容量乘以100转化为整数。改变状态定义如果价值是浮点数而重量是整数那么DP数组的值可以是double类型状态转移方程不变。交换维度如果重量范围很大但价值范围较小可以考虑用dp[i][v]表示考虑前i个物品总价值恰好为v时的最小重量然后找满足dp[n][v] capacity的最大v。这需要根据具体问题灵活变通。5.3 空间优化中的遍历顺序这是最经典的错误。一定要记住0-1背包一维DP内层循环必须倒序从大到小遍历容量。我见过无数人在这里栽跟头写成了完全背包。如果你不确定就画一个简单的例子比如容量5物品(2,3),(3,4)手动模拟一下两种遍历顺序立刻就能看出区别。5.4 初始化陷阱“恰好装满” vs “不要求装满”。我们上面讨论的都是“不要求恰好装满”只要不超过容量就行。所以初始化时dp[0...capacity] 0表示在任何容量下什么都不装的价值是0合法状态。 但有一类变种问题是“要求恰好装满背包”此时初始化就不同了dp[0] 0容量为0时恰好装满的价值为0合法。dp[1...capacity] -INF用一个很小的数比如INT_MIN表示其他容量在初始状态下“无法恰好装满”是一个非法状态。在状态转移时只有从合法状态非-INF转移过来的才是合法的。// 恰好装满背包的最大价值 int knapsackExactlyFull(int capacity, const vectorint weights, const vectorint values) { vectorint dp(capacity 1, INT_MIN); // 初始化为负无穷 dp[0] 0; // 容量为0时恰好装满的价值为0 for (int i 0; i weights.size(); i) { int w weights[i], v values[i]; for (int c capacity; c w; --c) { if (dp[c - w] ! INT_MIN) { // 只有前一个状态是合法的才能转移 dp[c] max(dp[c], v dp[c - w]); } } } // 如果dp[capacity]仍然是INT_MIN说明无法恰好装满 return dp[capacity] INT_MIN ? -1 : dp[capacity]; }6. 变种问题与实战联想0-1背包的模型非常基础但它的变体层出不穷是面试和竞赛中的常客。理解核心模型后这些变体大多可以通过修改状态定义或转移方程来解决。6.1 分割等和子集LeetCode 416问题给定一个只包含正整数的非空数组判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。转化这等价于从数组中选一些数使得它们的和等于整个数组和的一半记作target。每个数字只能选一次。这就是一个0-1背包问题背包容量是target物品的重量和价值都是数组中的数字。我们只需要判断最大价值是否恰好等于target不这里我们关心的是“能否恰好装满”。所以用“恰好装满”的DPdp[c]表示容量c能否被恰好装满布尔值。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; for (int num : nums) { for (int c target; c num; --c) { dp[c] dp[c] || dp[c - num]; // 不选 或 选 } } return dp[target]; }6.2 目标和LeetCode 494问题给定一个整数数组和一个目标数S你可以在每个数字前添加或-号使得表达式结果等于S。求有多少种添加符号的方法。转化设所有带号的数和为P带-号的数和为N绝对值则有P - N S且P N sum数组总和。解方程得P (S sum) / 2。问题转化为从数组中选若干个数使得它们的和恰好等于(S sum) / 2有多少种选法这是一个计数类的0-1背包问题。dp[c]表示凑成总和c的方案数。状态转移dp[c] dp[c - num]当c num时。int findTargetSumWays(vectorint nums, int S) { int sum accumulate(nums.begin(), nums.end(), 0); if (sum S || (S sum) % 2 ! 0) return 0; int target (S sum) / 2; vectorint dp(target 1, 0); dp[0] 1; // 凑成0的方案有1种什么都不选 for (int num : nums) { for (int c target; c num; --c) { dp[c] dp[c - num]; } } return dp[target]; }6.3 盈利计划LeetCode 879这是一个二维费用的背包问题。每个工作有两个维度所需人数group[i]和产生的利润profit[i]。总人数限制为G要求至少产生P的利润。求有多少种选择方案。这需要将“至少产生P利润”这个条件转化为状态。我们可以定义dp[g][p]为使用恰好g个人产生至少p利润的方案数。或者更巧妙的定义dp[g][p]为使用不超过g个人产生至少p利润的方案数。状态转移需要仔细考虑“至少”这个条件通常将超过P的利润都压缩到P这个状态上即min(p profit[i], P)。7. 完整可运行源码示例与性能考量最后贴上一份完整的、包含多种解法和详细注释的C源码你可以直接复制到本地编译器运行测试。#include iostream #include vector #include algorithm #include numeric #include climits using namespace std; // 方法1暴力递归仅用于理解n20会极慢 int knapsackBruteForce(int cap, const vectorint w, const vectorint v, int idx) { if (idx 0 || cap 0) return 0; int notTake knapsackBruteForce(cap, w, v, idx - 1); int take (w[idx] cap) ? v[idx] knapsackBruteForce(cap - w[idx], w, v, idx - 1) : 0; return max(take, notTake); } // 方法2记忆化搜索 int knapsackMemo(int cap, const vectorint w, const vectorint v, int idx, vectorvectorint memo) { if (idx 0 || cap 0) return 0; if (memo[idx][cap] ! -1) return memo[idx][cap]; int notTake knapsackMemo(cap, w, v, idx - 1, memo); int take (w[idx] cap) ? v[idx] knapsackMemo(cap - w[idx], w, v, idx - 1, memo) : 0; return memo[idx][cap] max(take, notTake); } // 方法3经典二维动态规划 int knapsack2D(int capacity, const vectorint weights, const vectorint values) { int n weights.size(); vectorvectorint dp(n 1, vectorint(capacity 1, 0)); for (int i 1; i n; i) { int w weights[i - 1], v values[i - 1]; for (int c 1; c capacity; c) { dp[i][c] dp[i - 1][c]; // 不选 if (c w) { dp[i][c] max(dp[i][c], v dp[i - 1][c - w]); // 选 } } } return dp[n][capacity]; } // 方法4空间优化一维DP最常用模板 int knapsack1D(int capacity, const vectorint weights, const vectorint values) { vectorint dp(capacity 1, 0); for (int i 0; i weights.size(); i) { int w weights[i], v values[i]; // 必须倒序 for (int c capacity; c w; --c) { dp[c] max(dp[c], v dp[c - w]); } } return dp[capacity]; } // 方法5恰好装满背包的最大价值 int knapsackExactly(int capacity, const vectorint weights, const vectorint values) { vectorint dp(capacity 1, INT_MIN); dp[0] 0; for (int i 0; i weights.size(); i) { int w weights[i], v values[i]; for (int c capacity; c w; --c) { if (dp[c - w] ! INT_MIN) { dp[c] max(dp[c], v dp[c - w]); } } } return dp[capacity] INT_MIN ? -1 : dp[capacity]; } // 工具函数从二维DP表回溯选择的物品 vectorint traceSolution(int capacity, const vectorint weights, const vectorint values, const vectorvectorint dp) { int n weights.size(); vectorint selected; int c capacity; for (int i n; i 0 c 0; --i) { if (dp[i][c] ! dp[i - 1][c]) { selected.push_back(i - 1); c - weights[i - 1]; } } reverse(selected.begin(), selected.end()); // 可选使顺序为正序 return selected; } int main() { // 示例数据 vectorint weights {2, 3, 4, 5, 7}; vectorint values {3, 4, 5, 6, 8}; int capacity 10; cout 背包容量: capacity endl; cout 物品重量: ; for (int w : weights) cout w ; cout endl; cout 物品价值: ; for (int v : values) cout v ; cout endl endl; // 测试不同方法 cout [1] 暴力递归结果: knapsackBruteForce(capacity, weights, values, weights.size() - 1) endl; vectorvectorint memo(weights.size(), vectorint(capacity 1, -1)); cout [2] 记忆化搜索结果: knapsackMemo(capacity, weights, values, weights.size() - 1, memo) endl; cout [3] 二维DP结果: knapsack2D(capacity, weights, values) endl; cout [4] 一维DP结果: knapsack1D(capacity, weights, values) endl; cout [5] 恰好装满结果: knapsackExactly(capacity, weights, values) endl; // 回溯方案演示 cout \n--- 回溯具体方案 --- endl; vectorvectorint dp2d(weights.size() 1, vectorint(capacity 1, 0)); // 重新计算二维表用于回溯 for (int i 1; i weights.size(); i) { int w weights[i - 1], v values[i - 1]; for (int c 1; c capacity; c) { dp2d[i][c] dp2d[i - 1][c]; if (c w) dp2d[i][c] max(dp2d[i][c], v dp2d[i - 1][c - w]); } } cout 最大价值 (从二维表读): dp2d[weights.size()][capacity] endl; vectorint chosen traceSolution(capacity, weights, values, dp2d); cout 选中的物品索引: ; for (int idx : chosen) cout idx ; cout endl; cout 对应重量/价值: ; int totalW 0, totalV 0; for (int idx : chosen) { cout ( weights[idx] , values[idx] ) ; totalW weights[idx]; totalV values[idx]; } cout endl; cout 总重量: totalW , 总价值: totalV endl; return 0; }性能考量0-1背包DP的时间复杂度是O(n * capacity)。这里的capacity是背包容量如果容量非常大比如10^9而物品数量n较小比如100那么O(n * capacity)的算法是无法接受的。这种情况下就需要考虑上面提到的交换维度的方法或者使用其他算法如Meet-in-the-Middle折半搜索。对于面试和笔试掌握基础的DP和其优化已经能解决大部分问题但知道这些边界和更优解的存在能体现你的知识深度。算法学习理解原理比背诵代码重要十倍。0-1背包问题就像一块坚实的基石把它吃透了很多复杂的动态规划问题你都能找到相似的影子。希望这篇长文能帮你把这基石打得更牢一些。在实际编码时如果遇到变种问题卡壳不妨回到最经典的模型想想状态怎么定义、决策有哪些、方程怎么列思路往往就会清晰起来。