开头部分先从很多人对贪心算法的“过度信任”切入。贪心算法是算法竞赛和工程面试里最常见的思路但它在多背包问题上很容易翻车。这篇文章围绕贪心算法、多背包问题、C代码三个关键词讲清楚原理、完整例题演算、可直接用的代码以及贪心解和最优解的真实差距。适合正在学算法的学生、准备面试的开发者以及做资源分配类系统的工程师。写这篇的起因是前阵子有读者问我单背包问题用动态规划轻易就能解为什么多背包场景下没人写动态规划其实答案不复杂——多背包问题是倍数增长的组合优化问题精确解法成本很高工程上往往退而求其次用贪心。但贪心的坑很多排序指标、装载策略、背包顺序都会影响结果。我打算用一个完整实例从原理讲到代码最后把贪心的边界也一并说清楚。1. 多背包问题从单背包升级后难在哪里1.1 经典0-1背包的数学描述先回顾单背包。给定一个容量为C的背包和n件物品每件物品有重量w_i和价值v_i目标是选择若干物品装入背包使得总重量不超过C总价值最大。用数学语言写就是最大化Σ v_i * x_i 约束 Σ w_i * x_i ≤ C x_i ∈ {0, 1}这里的x_i是决策变量取1表示装入背包取0表示不装。它之所以叫“0-1背包”是因为每件物品只有装或者不装两种状态不能切割。单背包问题的标准解法是动态规划。定义dp[j]表示容量为j的背包能装下的最大价值状态转移方程是dp[j] max(dp[j], dp[j - w_i] v_i)对每件物品从高容量到低容量更新最终dp[C]就是答案。时间复杂度O(n·C)空间复杂度O(C)。这在n和C都不算大的时候非常实用。很多教材把这个作为动态规划入门题也正因为如此不少人会下意识觉得多背包问题也可以照搬这个套路。1.2 多背包问题的正式定义多背包问题可以看作单背包的一般化现在有m个背包容量分别是C_1, C_2, ..., C_m有n件物品每件同样有重量w_i和价值v_i。每件物品最多只能放入一个背包每个背包的总重量不能超过它的容量目标仍然是最大化所有背包的总价值。形式化定义最大化Σ_i (v_i * Σ_j x_{i,j}) 约束 Σ_i w_i * x_{i,j} ≤ C_j 每个背包的容量约束 Σ_j x_{i,j} ≤ 1 每件物品最多进一个背包 x_{i,j} ∈ {0, 1}这里的x_{i,j}表示物品i是否放入背包j。注意物品不允许分拆也不能同时出现在两个背包里。只看公式可能不够直观。你可以把场景替换成实际的业务一个物流车队的每辆卡车有不同载重上限一批货物有重量也有收益怎么分配才能让总收益最大或者云平台上一组服务器各有不同内存一批任务有内存占用也有执行价值怎么分配才能让整体利用率最高。这就是多背包问题的典型形态。1.3 为什么说它是NP-hard多背包问题属于组合优化里的NP-hard问题。这句话的实际含义是当物品数量和背包数量增长时目前不存在一个可以在多项式时间内求出全局最优解的算法。这里说“不存在”是指基于P≠NP这一被广泛接受的假设下不存在而不是还没找到。所有精确解法在最坏情况下的复杂度都会随规模指数增长。为什么它比单背包难那么多单背包的状态只有一个维度——背包剩余容量动态规划可以把容量作为状态完整枚举。多背包的状态变成m个剩余容量组成的向量理论上DP维度也会变成m维状态量直接爆炸。比如3个容量均为100的背包如果用容量维度枚举需要100×100×100100万个状态这还算能接受如果背包数量到5、6个状态量就上亿了再乘上物品数量基本不现实。等到背包数量进一步增加精确求解基本没有还手余地。所以工程实践里很少去追求多背包问题的严格最优解而是退而求其次在“解质量”和“计算时间”之间做平衡。贪心算法就是其中最朴素、最常用的一种近似手段。接下来的核心问题是贪心策略怎么设计才不至于让结果差得太离谱。2. 贪心策略的选择只排序远远不够贪心算法的本质是每一步都做当前看起来最优的选择不回头、不反悔。对应到多背包问题上有两个决策点先决定按什么顺序处理物品再决定把当前物品放进哪个背包。这两个决策点的策略选择决定了最终解的质量上限。2.1 三种可选的贪心指标处理物品顺序时常见的贪心指标有三个指标排序方式直觉按价值降序先处理价值最高的物品优先抓住高价值货按重量升序先处理重量最轻的物品先把零碎小件填进去按价值密度降序先处理单位重量价值最高的物品优先装“性价比”最高的货价值密度就是v_i / w_i表示每单位重量能带来多少价值。这个指标最早在分数背包问题里出现——如果物品可以切割按价值密度从高到低装就能得到全局最优解。多背包虽然不允许切割但这个排序思想仍然被广泛沿用。2.2 只看价值和只看重量的翻车现场先看一个“只看价值”的失败例子。一个背包容量10三件物品物品A重量8价值20物品B重量4价值12物品C重量5价值11按价值降序先装A剩余容量2B和C都放不下总价值20。但最优解是装B和C重量9总价值23。为什么因为A虽然单价高但它体积太大占了太多空间导致后续有价值的物品全部进不来。贪心只看到了眼前的价值没有给后续物品留出空间。再看“只看重量”的例子。一个背包容量10有多件物品物品A重量5价值10物品B重量5价值9还有6件小物品每件重量1价值1按重量升序会先装6件小物品占用6剩余4A和B都放不下总价值6。最优解是直接装A和B重量10总价值19。只看重量会让人捡了一堆芝麻却丢掉了西瓜。这两个例子说明了一个核心教训贪心指标片面的话会产生“空间挤占”问题。高价值的可能体积大高性价比的也可能体积大若不考虑后续空间很容易把背包卡死。2.3 价值密度排序为什么是默认答案价值密度排序在大多数情况下表现最好原因可以这么理解它把“价值”和“重量”两个维度压缩成一个指标每一步都选单位重量价值最高的物品相当于在有限的容量里尽量买“性价比”最高的东西。在分数背包问题里这个策略已经被证明是最优的。整数0-1背包里它虽然不是严格最优但绝大多数随机数据下都能给出接近最优的解。工程上做近似算法默认先按价值密度排序是一个比较安全的起点。不过这里需要注意价值密度排序也会遇到反例。特别是有几件物品密度接近、但重量差异很大时贪心可能会因为先装了一个密度略高的大件而错过后面两个密度略低的组合。这种情况我后面会用完整例题演示。所以在实际使用中价值密度排序只是起点还需要配合合理的装载规则以及后续的优化策略。2.4 多背包还有一个“放哪个背包”的问题三种装载规则排序只是解决了“先处理谁”的问题。真正到了多背包场景还有一个单背包里不存在的新决策当前物品应该放入哪个背包。常见的装载规则有三种首次适应从头开始找第一个剩余容量足够放下当前物品的背包立刻放入。最佳适应遍历所有背包找剩余容量最小的那个能放下的背包放入目的是不浪费大背包的空间。最差适应找剩余容量最大的背包放入目的是把大背包空间用掉之后还能继续接受大件。在多背包问题里我个人的倾向是优先尝试最佳适应。原因是多背包的总容量是一定的最佳适应可以让每个背包的碎片空间尽量少避免出现“每个背包都剩一点但所有物品都放不下”的窘境。首次适应代码最简单、开销最小在背包数量很少时结果通常也不差。最差适应一般不推荐因为把空间先耗完后面一旦出现大件就无处安放但在一些特定数据集上它反而有奇效比如物品重量分布比较均匀、大件不多时。这三种规则不是互斥的你可以都实现一遍在同一份数据上跑对比结果再选。后面给的完整代码会同时支持首次适应和最佳适应用宏切换。3. 一道带容量限制的例题手算全程3.1 数据准备光讲理论不够我准备了一组能同时演示流程和暴露贪心短板的数据。假设有3个背包容量分别是12、8、5有8件物品重量和价值如下物品编号重量价值价值密度v/w14102.502284.0036183.004133.0057202.866362.0075153.0084123.00总容量128525所有物品总重量32所以肯定有一部分物品无法装入。现在按照“价值密度降序 最佳适应”的贪心策略来手动演算一遍。3.2 按密度排序后的物品顺序先计算价值密度然后降序排列。物品2密度最高排第一物品3、4、7、8密度相同都是3.00按原编号顺序处理物品5密度2.86物品1密度2.50物品6密度2.00。因此处理顺序是物品2 → 物品3 → 物品4 → 物品7 → 物品8 → 物品5 → 物品1 → 物品63.3 逐步分配过程最佳适应三个背包初始状态背包1剩余12背包2剩余8背包3剩余5。物品2重量2价值8三个背包都能装下。最佳适应要找剩余容量最小的放入后剩余容量分别为背包1剩10背包2剩6背包3剩3。剩余最小的是背包3装入背包3背包3剩余3。物品3重量6价值18背包3剩余3放不下背包2剩余8刚好能装装完后剩2背包1装完剩6。最紧的是背包2装入背包2背包2剩余2。物品4重量1价值3三个背包都能装。装完后剩余分别背包1剩11背包2剩1背包3剩2。最紧的是背包2装入背包2背包2剩余1。物品7重量5价值15背包2剩余1、背包3剩余3都放不下只能放背包1。装入后背包1剩余7。物品8重量4价值12背包2、背包3都放不下背包1剩余7可以放。装入后背包1剩余3。物品5重量7价值20此时背包1剩余3背包2剩余1背包3剩余3全部放不下跳过。物品1重量4价值10同样所有背包都放不下跳过。物品6重量3价值6背包1剩余3刚好可以放装入后背包1剩余0。最终分配结果背包容量装入物品已用重量背包价值背包112物品7、物品8、物品6121512633背包28物品3、物品4718321背包35物品228总价值3321862总重量127221剩余容量4。3.4 结果与最优解对比贪心解是62。但是我手动调整一下可以得到一个更好的可行解背包容量装入物品已用重量背包价值背包112物品3、物品7、物品4121815336背包28物品5720背包35物品2、物品658614总价值36201470总重量127524剩余容量1。70比62多了8提升幅度约12.9%。这里问题出在哪贪心处理物品8时因为它的密度是3.00和物品3、物品7一样但排序靠后它被塞进了背包1占掉了剩余空间。结果真正的“高价值大件”物品5进不来了而物品8的价值12远不如物品5的20。如果把物品8拿走把物品5放进去总价值立刻上涨。这说明在密度相同或接近的局部区域贪心的先后顺序会严重影响结果。所以这篇例题想传达两件事第一贪心的完整流程很好理解手算一遍就能掌握第二贪心解即使很接近最优也可能因为局部的先后顺序错失更优方案。这也是后续章节讨论边界和改进的原因。4. 完整C代码实现与关键代码段拆解4.1 数据结构设计C语言实现首先要定义两个结构体物品和背包。物品结构体包含编号、重量、价值、价值密度以及最终装入的目标背包编号。密度在排序前算一次后续比较直接用浮点数目标背包编号初始化为-1表示还没装入任何背包。typedef struct { int id; int w; int v; double density; int bin; // 装入哪个背包-1表示未装入 } Item;背包结构体只需要容量和已使用容量剩余容量通过cap - used计算typedef struct { int cap; int used; } Bin;这里我特意把背包的剩余容量设计成动态计算而不是单独存一个remain字段。原因是分配过程中used一直在变化直接算剩余比维护多个字段省心也不容易出错。4.2 排序与分配主逻辑排序用C标准库的qsort比较函数按价值密度降序。一个容易踩坑的细节是浮点数比较不能直接用减法返回差值因为qsort的比较函数要求返回负、零、正三个状态浮点减法可能因为精度问题产生错误状态。更稳的写法是int cmp_by_density(const void *a, const void *b) { const Item *x (const Item *)a; const Item *y (const Item *)b; return (y-density x-density) - (y-density x-density); }这个写法返回三个整数值不依赖浮点差值稳定可靠。分配主逻辑是双重循环。外层遍历排好序的物品内层遍历所有背包根据装载规则选出目标背包。我加了USE_BEST_FIT宏来切换策略#define USE_BEST_FIT 1 // 1最佳适应0首次适应 for (int i 0; i ITEM_NUM; i) { int target -1; int best_remain 0; for (int j 0; j BIN_NUM; j) { int remain bins[j].cap - bins[j].used; if (remain items[i].w) { if (USE_BEST_FIT) { // 最佳适应找剩余容量最小且能放下的背包 if (target -1 || remain best_remain) { target j; best_remain remain; } } else { // 首次适应找第一个能放下的背包 target j; break; } } } if (target ! -1) { bins[target].used items[i].w; items[i].bin target; } }首次适应只需要第一个满足条件的背包所以内层break跳出最佳适应需要遍历所有背包不断更新最小剩余容量。在实际工程中如果背包数量很大最佳适应的O(n·m)开销可能成为瓶颈可以考虑用平衡树或优先队列维护剩余容量把内层查找降到O(log m)。不过在小规模数据和入门场景下直接的O(n·m)遍历已经完全够用。4.3 完整可运行代码下面是完整代码可以直接复制编译运行。初始化部分直接使用前面例题的数据方便对照验证#include stdio.h #include stdlib.h #define ITEM_NUM 8 #define BIN_NUM 3 #define USE_BEST_FIT 1 // 1最佳适应0首次适应 typedef struct { int id; int w; int v; double density; int bin; // 装入哪个背包-1表示未装入 } Item; typedef struct { int cap; int used; } Bin; int cmp_by_density(const void *a, const void *b) { const Item *x (const Item *)a; const Item *y (const Item *)b; return (y-density x-density) - (y-density x-density); } int main(void) { Item items[ITEM_NUM] { {1, 4, 10, 0.0, -1}, {2, 2, 8, 0.0, -1}, {3, 6, 18, 0.0, -1}, {4, 1, 3, 0.0, -1}, {5, 7, 20, 0.0, -1}, {6, 3, 6, 0.0, -1}, {7, 5, 15, 0.0, -1}, {8, 4, 12, 0.0, -1} }; Bin bins[BIN_NUM] { {12, 0}, {8, 0}, {5, 0} }; // 计算价值密度 for (int i 0; i ITEM_NUM; i) { items[i].density (double)items[i].v / items[i].w; } // 按价值密度降序排序 qsort(items, ITEM_NUM, sizeof(Item), cmp_by_density); printf(按价值密度降序排列后的物品\n); for (int i 0; i ITEM_NUM; i) { printf( 物品%d: 重量%2d, 价值%2d, 密度%.2f\n, items[i].id, items[i].w, items[i].v, items[i].density); } printf(\n); // 贪心分配 for (int i 0; i ITEM_NUM; i) { int target -1; int best_remain 0; for (int j 0; j BIN_NUM; j) { int remain bins[j].cap - bins[j].used; if (remain items[i].w) { if (USE_BEST_FIT) { if (target -1 || remain best_remain) { target j; best_remain remain; } } else { target j; break; } } } if (target ! -1) { bins[target].used items[i].w; items[i].bin target; printf(物品%d(重量%d,价值%d) - 背包%d剩余容量%d\n, items[i].id, items[i].w, items[i].v, target 1, bins[target].cap - bins[target].used); } else { printf(物品%d(重量%d,价值%d) 找不到能装下的背包被跳过\n, items[i].id, items[i].w, items[i].v); } } // 输出结果 int total_value 0; int total_weight 0; printf(\n 最终分配结果 \n); for (int j 0; j BIN_NUM; j) { int bin_value 0; int bin_weight 0; printf(背包%d容量%d已用%d剩余%d\n, j 1, bins[j].cap, bins[j].used, bins[j].cap - bins[j].used); printf( 装入物品); for (int i 0; i ITEM_NUM; i) { if (items[i].bin j) { printf(物品%d , items[i].id); bin_value items[i].v; bin_weight items[i].w; } } printf(\n 背包价值%d重量%d\n, bin_value, bin_weight); total_value bin_value; total_weight bin_weight; } printf(\n总价值%d总重量%d\n, total_value, total_weight); return 0; }运行这段代码会得到和第3章手算一致的输出物品2进背包3物品3进背包2物品4进背包2物品7进背包1物品8进背包1物品5和物品1被跳过物品6进背包1总价值62。如果你想看首次适应的效果把USE_BEST_FIT改成0重新编译即可。4.4 时间、空间复杂度分析这段代码的时间复杂度由两部分组成排序O(n log n)分配过程O(n·m)。在n和m都不大的场景下非常快。空间复杂度是O(n m)主要开销是物品数组和背包数组。如果要在超大规模场景下使用需要注意物品数组的额外字段比较多每个物品多了一个double和几个int内存占用总体可控。真到了百万级物品可能就要改成流式读取、分批处理避免一次性载入内存。5. 贪心的边界什么场景下它值得用5.1 为什么贪心解不是最优解理论层面的原因贪心算法的核心假设是“局部最优能推出全局最优”但这个假设在0-1背包类问题里通常不成立。原因在于物品的不可分割性和容量约束的联动性。每次装一个物品都会改变所有背包的剩余容量影响后续所有物品的选择空间。贪心在每一步只看到当前密度最高的物品看不到这个选择对全局组合空间的影响。前面例题就是典型的密度相似场景物品3、物品7、物品8的密度都是3.00排序先后几乎决定命运。物品8因为排在物品5前面先进了背包1实际结果是它挤掉了后来的物品5。这类问题在密度排序的局部区域非常容易发生尤其是当多个物品密度接近时排序的微小差异可能带来完全不同的解。5.2 与动态规划方法的复杂度对比单背包问题的动态规划复杂度是O(n·C)空间O(C)。多背包如果直接扩展状态维度复杂度会变成O(n·C_1·C_2·...·C_m)量级背包数量一多直接不可用。精确算法中还有分支限界法通过深度优先搜索和剪枝来寻找最优解但在最坏情况下仍然是指数级。所以选择什么算法取决于问题规模和要求场景推荐方案单背包容量适中动态规划严格最优多背包规模很小m≤3可以尝试搜索或动态规划多背包规模大贪心快速出解或贪心局部搜索多背包要求严格最优整数规划求解器成本高从实际经验看如果只是算法题题目没明确要求最优解贪心通常能拿比较可观的分数如果是工程系统我更建议用贪心作为初始解再叠加一轮局部搜索性价比最高。5.3 工程中怎么用贪心三种实用改进第一种是多次随机化贪心。排序时遇到密度相同的物品固定顺序会带来偏差可以随机打乱这些平局物品的顺序运行多次取最好结果。代价只是多几次循环收获往往不小。第二种是贪心后的局部搜索。得到一个贪心解之后检查是否有这样的机会把一个背包里价值较低的物品拿出来换入另一件当前未装入但价值更高的物品同时保证两个背包都不超容量。这种交换操作每做一次总价值就提高一次代码也不复杂。实际项目里这个“贪心初解交换优化”的组合比单纯贪心质量高得多。第三种是两轮分配。第一轮先把密度高的物品按贪心思路放第二轮把剩余物品按体积从小到大重新放一遍。这种策略适合物品重量范围特别大的场景能减少碎片空间。5.4 经验判断我早年在做一个货运装载的排程系统时背包不是三个而是几十辆车货物也有数千件。最开始就只用贪心生成结果很快但业务方觉得总价值不够高。后来加了局部搜索和随机重启解的质量提升明显通常能跑到接近整数规划求解器的结果耗时却只有几秒。这个经历给我的体会是不要迷信贪心也不要一杆子打死贪心。它最合适的位置是作为“快速初始解生成器”配合一轮局部优化在质量和性能之间取得平衡。如果只是自己写代码练习我建议你把这套代码跑通之后把USE_BEST_FIT切换一下看看同样数据下结果差多少再改一改物品数据感受一下不同数据分布对结果的影响。这种手感比死记理论有用得多。最后说一个容易忽略的点贪心算法的代码即使逻辑再简单也一定要在输出里保留完整的装入明细而不是只输出总价值。我之前排查一个分配异常时就靠“哪个物品进了哪个背包”的日志才定位到是排序比较函数写错导致密度倒排。能看到中间过程比只看最终数字重要得多。 多背包问题贪心算法详解：C代码实现与最优解差距分析
开头部分先从很多人对贪心算法的“过度信任”切入。贪心算法是算法竞赛和工程面试里最常见的思路但它在多背包问题上很容易翻车。这篇文章围绕贪心算法、多背包问题、C代码三个关键词讲清楚原理、完整例题演算、可直接用的代码以及贪心解和最优解的真实差距。适合正在学算法的学生、准备面试的开发者以及做资源分配类系统的工程师。写这篇的起因是前阵子有读者问我单背包问题用动态规划轻易就能解为什么多背包场景下没人写动态规划其实答案不复杂——多背包问题是倍数增长的组合优化问题精确解法成本很高工程上往往退而求其次用贪心。但贪心的坑很多排序指标、装载策略、背包顺序都会影响结果。我打算用一个完整实例从原理讲到代码最后把贪心的边界也一并说清楚。1. 多背包问题从单背包升级后难在哪里1.1 经典0-1背包的数学描述先回顾单背包。给定一个容量为C的背包和n件物品每件物品有重量w_i和价值v_i目标是选择若干物品装入背包使得总重量不超过C总价值最大。用数学语言写就是最大化Σ v_i * x_i 约束 Σ w_i * x_i ≤ C x_i ∈ {0, 1}这里的x_i是决策变量取1表示装入背包取0表示不装。它之所以叫“0-1背包”是因为每件物品只有装或者不装两种状态不能切割。单背包问题的标准解法是动态规划。定义dp[j]表示容量为j的背包能装下的最大价值状态转移方程是dp[j] max(dp[j], dp[j - w_i] v_i)对每件物品从高容量到低容量更新最终dp[C]就是答案。时间复杂度O(n·C)空间复杂度O(C)。这在n和C都不算大的时候非常实用。很多教材把这个作为动态规划入门题也正因为如此不少人会下意识觉得多背包问题也可以照搬这个套路。1.2 多背包问题的正式定义多背包问题可以看作单背包的一般化现在有m个背包容量分别是C_1, C_2, ..., C_m有n件物品每件同样有重量w_i和价值v_i。每件物品最多只能放入一个背包每个背包的总重量不能超过它的容量目标仍然是最大化所有背包的总价值。形式化定义最大化Σ_i (v_i * Σ_j x_{i,j}) 约束 Σ_i w_i * x_{i,j} ≤ C_j 每个背包的容量约束 Σ_j x_{i,j} ≤ 1 每件物品最多进一个背包 x_{i,j} ∈ {0, 1}这里的x_{i,j}表示物品i是否放入背包j。注意物品不允许分拆也不能同时出现在两个背包里。只看公式可能不够直观。你可以把场景替换成实际的业务一个物流车队的每辆卡车有不同载重上限一批货物有重量也有收益怎么分配才能让总收益最大或者云平台上一组服务器各有不同内存一批任务有内存占用也有执行价值怎么分配才能让整体利用率最高。这就是多背包问题的典型形态。1.3 为什么说它是NP-hard多背包问题属于组合优化里的NP-hard问题。这句话的实际含义是当物品数量和背包数量增长时目前不存在一个可以在多项式时间内求出全局最优解的算法。这里说“不存在”是指基于P≠NP这一被广泛接受的假设下不存在而不是还没找到。所有精确解法在最坏情况下的复杂度都会随规模指数增长。为什么它比单背包难那么多单背包的状态只有一个维度——背包剩余容量动态规划可以把容量作为状态完整枚举。多背包的状态变成m个剩余容量组成的向量理论上DP维度也会变成m维状态量直接爆炸。比如3个容量均为100的背包如果用容量维度枚举需要100×100×100100万个状态这还算能接受如果背包数量到5、6个状态量就上亿了再乘上物品数量基本不现实。等到背包数量进一步增加精确求解基本没有还手余地。所以工程实践里很少去追求多背包问题的严格最优解而是退而求其次在“解质量”和“计算时间”之间做平衡。贪心算法就是其中最朴素、最常用的一种近似手段。接下来的核心问题是贪心策略怎么设计才不至于让结果差得太离谱。2. 贪心策略的选择只排序远远不够贪心算法的本质是每一步都做当前看起来最优的选择不回头、不反悔。对应到多背包问题上有两个决策点先决定按什么顺序处理物品再决定把当前物品放进哪个背包。这两个决策点的策略选择决定了最终解的质量上限。2.1 三种可选的贪心指标处理物品顺序时常见的贪心指标有三个指标排序方式直觉按价值降序先处理价值最高的物品优先抓住高价值货按重量升序先处理重量最轻的物品先把零碎小件填进去按价值密度降序先处理单位重量价值最高的物品优先装“性价比”最高的货价值密度就是v_i / w_i表示每单位重量能带来多少价值。这个指标最早在分数背包问题里出现——如果物品可以切割按价值密度从高到低装就能得到全局最优解。多背包虽然不允许切割但这个排序思想仍然被广泛沿用。2.2 只看价值和只看重量的翻车现场先看一个“只看价值”的失败例子。一个背包容量10三件物品物品A重量8价值20物品B重量4价值12物品C重量5价值11按价值降序先装A剩余容量2B和C都放不下总价值20。但最优解是装B和C重量9总价值23。为什么因为A虽然单价高但它体积太大占了太多空间导致后续有价值的物品全部进不来。贪心只看到了眼前的价值没有给后续物品留出空间。再看“只看重量”的例子。一个背包容量10有多件物品物品A重量5价值10物品B重量5价值9还有6件小物品每件重量1价值1按重量升序会先装6件小物品占用6剩余4A和B都放不下总价值6。最优解是直接装A和B重量10总价值19。只看重量会让人捡了一堆芝麻却丢掉了西瓜。这两个例子说明了一个核心教训贪心指标片面的话会产生“空间挤占”问题。高价值的可能体积大高性价比的也可能体积大若不考虑后续空间很容易把背包卡死。2.3 价值密度排序为什么是默认答案价值密度排序在大多数情况下表现最好原因可以这么理解它把“价值”和“重量”两个维度压缩成一个指标每一步都选单位重量价值最高的物品相当于在有限的容量里尽量买“性价比”最高的东西。在分数背包问题里这个策略已经被证明是最优的。整数0-1背包里它虽然不是严格最优但绝大多数随机数据下都能给出接近最优的解。工程上做近似算法默认先按价值密度排序是一个比较安全的起点。不过这里需要注意价值密度排序也会遇到反例。特别是有几件物品密度接近、但重量差异很大时贪心可能会因为先装了一个密度略高的大件而错过后面两个密度略低的组合。这种情况我后面会用完整例题演示。所以在实际使用中价值密度排序只是起点还需要配合合理的装载规则以及后续的优化策略。2.4 多背包还有一个“放哪个背包”的问题三种装载规则排序只是解决了“先处理谁”的问题。真正到了多背包场景还有一个单背包里不存在的新决策当前物品应该放入哪个背包。常见的装载规则有三种首次适应从头开始找第一个剩余容量足够放下当前物品的背包立刻放入。最佳适应遍历所有背包找剩余容量最小的那个能放下的背包放入目的是不浪费大背包的空间。最差适应找剩余容量最大的背包放入目的是把大背包空间用掉之后还能继续接受大件。在多背包问题里我个人的倾向是优先尝试最佳适应。原因是多背包的总容量是一定的最佳适应可以让每个背包的碎片空间尽量少避免出现“每个背包都剩一点但所有物品都放不下”的窘境。首次适应代码最简单、开销最小在背包数量很少时结果通常也不差。最差适应一般不推荐因为把空间先耗完后面一旦出现大件就无处安放但在一些特定数据集上它反而有奇效比如物品重量分布比较均匀、大件不多时。这三种规则不是互斥的你可以都实现一遍在同一份数据上跑对比结果再选。后面给的完整代码会同时支持首次适应和最佳适应用宏切换。3. 一道带容量限制的例题手算全程3.1 数据准备光讲理论不够我准备了一组能同时演示流程和暴露贪心短板的数据。假设有3个背包容量分别是12、8、5有8件物品重量和价值如下物品编号重量价值价值密度v/w14102.502284.0036183.004133.0057202.866362.0075153.0084123.00总容量128525所有物品总重量32所以肯定有一部分物品无法装入。现在按照“价值密度降序 最佳适应”的贪心策略来手动演算一遍。3.2 按密度排序后的物品顺序先计算价值密度然后降序排列。物品2密度最高排第一物品3、4、7、8密度相同都是3.00按原编号顺序处理物品5密度2.86物品1密度2.50物品6密度2.00。因此处理顺序是物品2 → 物品3 → 物品4 → 物品7 → 物品8 → 物品5 → 物品1 → 物品63.3 逐步分配过程最佳适应三个背包初始状态背包1剩余12背包2剩余8背包3剩余5。物品2重量2价值8三个背包都能装下。最佳适应要找剩余容量最小的放入后剩余容量分别为背包1剩10背包2剩6背包3剩3。剩余最小的是背包3装入背包3背包3剩余3。物品3重量6价值18背包3剩余3放不下背包2剩余8刚好能装装完后剩2背包1装完剩6。最紧的是背包2装入背包2背包2剩余2。物品4重量1价值3三个背包都能装。装完后剩余分别背包1剩11背包2剩1背包3剩2。最紧的是背包2装入背包2背包2剩余1。物品7重量5价值15背包2剩余1、背包3剩余3都放不下只能放背包1。装入后背包1剩余7。物品8重量4价值12背包2、背包3都放不下背包1剩余7可以放。装入后背包1剩余3。物品5重量7价值20此时背包1剩余3背包2剩余1背包3剩余3全部放不下跳过。物品1重量4价值10同样所有背包都放不下跳过。物品6重量3价值6背包1剩余3刚好可以放装入后背包1剩余0。最终分配结果背包容量装入物品已用重量背包价值背包112物品7、物品8、物品6121512633背包28物品3、物品4718321背包35物品228总价值3321862总重量127221剩余容量4。3.4 结果与最优解对比贪心解是62。但是我手动调整一下可以得到一个更好的可行解背包容量装入物品已用重量背包价值背包112物品3、物品7、物品4121815336背包28物品5720背包35物品2、物品658614总价值36201470总重量127524剩余容量1。70比62多了8提升幅度约12.9%。这里问题出在哪贪心处理物品8时因为它的密度是3.00和物品3、物品7一样但排序靠后它被塞进了背包1占掉了剩余空间。结果真正的“高价值大件”物品5进不来了而物品8的价值12远不如物品5的20。如果把物品8拿走把物品5放进去总价值立刻上涨。这说明在密度相同或接近的局部区域贪心的先后顺序会严重影响结果。所以这篇例题想传达两件事第一贪心的完整流程很好理解手算一遍就能掌握第二贪心解即使很接近最优也可能因为局部的先后顺序错失更优方案。这也是后续章节讨论边界和改进的原因。4. 完整C代码实现与关键代码段拆解4.1 数据结构设计C语言实现首先要定义两个结构体物品和背包。物品结构体包含编号、重量、价值、价值密度以及最终装入的目标背包编号。密度在排序前算一次后续比较直接用浮点数目标背包编号初始化为-1表示还没装入任何背包。typedef struct { int id; int w; int v; double density; int bin; // 装入哪个背包-1表示未装入 } Item;背包结构体只需要容量和已使用容量剩余容量通过cap - used计算typedef struct { int cap; int used; } Bin;这里我特意把背包的剩余容量设计成动态计算而不是单独存一个remain字段。原因是分配过程中used一直在变化直接算剩余比维护多个字段省心也不容易出错。4.2 排序与分配主逻辑排序用C标准库的qsort比较函数按价值密度降序。一个容易踩坑的细节是浮点数比较不能直接用减法返回差值因为qsort的比较函数要求返回负、零、正三个状态浮点减法可能因为精度问题产生错误状态。更稳的写法是int cmp_by_density(const void *a, const void *b) { const Item *x (const Item *)a; const Item *y (const Item *)b; return (y-density x-density) - (y-density x-density); }这个写法返回三个整数值不依赖浮点差值稳定可靠。分配主逻辑是双重循环。外层遍历排好序的物品内层遍历所有背包根据装载规则选出目标背包。我加了USE_BEST_FIT宏来切换策略#define USE_BEST_FIT 1 // 1最佳适应0首次适应 for (int i 0; i ITEM_NUM; i) { int target -1; int best_remain 0; for (int j 0; j BIN_NUM; j) { int remain bins[j].cap - bins[j].used; if (remain items[i].w) { if (USE_BEST_FIT) { // 最佳适应找剩余容量最小且能放下的背包 if (target -1 || remain best_remain) { target j; best_remain remain; } } else { // 首次适应找第一个能放下的背包 target j; break; } } } if (target ! -1) { bins[target].used items[i].w; items[i].bin target; } }首次适应只需要第一个满足条件的背包所以内层break跳出最佳适应需要遍历所有背包不断更新最小剩余容量。在实际工程中如果背包数量很大最佳适应的O(n·m)开销可能成为瓶颈可以考虑用平衡树或优先队列维护剩余容量把内层查找降到O(log m)。不过在小规模数据和入门场景下直接的O(n·m)遍历已经完全够用。4.3 完整可运行代码下面是完整代码可以直接复制编译运行。初始化部分直接使用前面例题的数据方便对照验证#include stdio.h #include stdlib.h #define ITEM_NUM 8 #define BIN_NUM 3 #define USE_BEST_FIT 1 // 1最佳适应0首次适应 typedef struct { int id; int w; int v; double density; int bin; // 装入哪个背包-1表示未装入 } Item; typedef struct { int cap; int used; } Bin; int cmp_by_density(const void *a, const void *b) { const Item *x (const Item *)a; const Item *y (const Item *)b; return (y-density x-density) - (y-density x-density); } int main(void) { Item items[ITEM_NUM] { {1, 4, 10, 0.0, -1}, {2, 2, 8, 0.0, -1}, {3, 6, 18, 0.0, -1}, {4, 1, 3, 0.0, -1}, {5, 7, 20, 0.0, -1}, {6, 3, 6, 0.0, -1}, {7, 5, 15, 0.0, -1}, {8, 4, 12, 0.0, -1} }; Bin bins[BIN_NUM] { {12, 0}, {8, 0}, {5, 0} }; // 计算价值密度 for (int i 0; i ITEM_NUM; i) { items[i].density (double)items[i].v / items[i].w; } // 按价值密度降序排序 qsort(items, ITEM_NUM, sizeof(Item), cmp_by_density); printf(按价值密度降序排列后的物品\n); for (int i 0; i ITEM_NUM; i) { printf( 物品%d: 重量%2d, 价值%2d, 密度%.2f\n, items[i].id, items[i].w, items[i].v, items[i].density); } printf(\n); // 贪心分配 for (int i 0; i ITEM_NUM; i) { int target -1; int best_remain 0; for (int j 0; j BIN_NUM; j) { int remain bins[j].cap - bins[j].used; if (remain items[i].w) { if (USE_BEST_FIT) { if (target -1 || remain best_remain) { target j; best_remain remain; } } else { target j; break; } } } if (target ! -1) { bins[target].used items[i].w; items[i].bin target; printf(物品%d(重量%d,价值%d) - 背包%d剩余容量%d\n, items[i].id, items[i].w, items[i].v, target 1, bins[target].cap - bins[target].used); } else { printf(物品%d(重量%d,价值%d) 找不到能装下的背包被跳过\n, items[i].id, items[i].w, items[i].v); } } // 输出结果 int total_value 0; int total_weight 0; printf(\n 最终分配结果 \n); for (int j 0; j BIN_NUM; j) { int bin_value 0; int bin_weight 0; printf(背包%d容量%d已用%d剩余%d\n, j 1, bins[j].cap, bins[j].used, bins[j].cap - bins[j].used); printf( 装入物品); for (int i 0; i ITEM_NUM; i) { if (items[i].bin j) { printf(物品%d , items[i].id); bin_value items[i].v; bin_weight items[i].w; } } printf(\n 背包价值%d重量%d\n, bin_value, bin_weight); total_value bin_value; total_weight bin_weight; } printf(\n总价值%d总重量%d\n, total_value, total_weight); return 0; }运行这段代码会得到和第3章手算一致的输出物品2进背包3物品3进背包2物品4进背包2物品7进背包1物品8进背包1物品5和物品1被跳过物品6进背包1总价值62。如果你想看首次适应的效果把USE_BEST_FIT改成0重新编译即可。4.4 时间、空间复杂度分析这段代码的时间复杂度由两部分组成排序O(n log n)分配过程O(n·m)。在n和m都不大的场景下非常快。空间复杂度是O(n m)主要开销是物品数组和背包数组。如果要在超大规模场景下使用需要注意物品数组的额外字段比较多每个物品多了一个double和几个int内存占用总体可控。真到了百万级物品可能就要改成流式读取、分批处理避免一次性载入内存。5. 贪心的边界什么场景下它值得用5.1 为什么贪心解不是最优解理论层面的原因贪心算法的核心假设是“局部最优能推出全局最优”但这个假设在0-1背包类问题里通常不成立。原因在于物品的不可分割性和容量约束的联动性。每次装一个物品都会改变所有背包的剩余容量影响后续所有物品的选择空间。贪心在每一步只看到当前密度最高的物品看不到这个选择对全局组合空间的影响。前面例题就是典型的密度相似场景物品3、物品7、物品8的密度都是3.00排序先后几乎决定命运。物品8因为排在物品5前面先进了背包1实际结果是它挤掉了后来的物品5。这类问题在密度排序的局部区域非常容易发生尤其是当多个物品密度接近时排序的微小差异可能带来完全不同的解。5.2 与动态规划方法的复杂度对比单背包问题的动态规划复杂度是O(n·C)空间O(C)。多背包如果直接扩展状态维度复杂度会变成O(n·C_1·C_2·...·C_m)量级背包数量一多直接不可用。精确算法中还有分支限界法通过深度优先搜索和剪枝来寻找最优解但在最坏情况下仍然是指数级。所以选择什么算法取决于问题规模和要求场景推荐方案单背包容量适中动态规划严格最优多背包规模很小m≤3可以尝试搜索或动态规划多背包规模大贪心快速出解或贪心局部搜索多背包要求严格最优整数规划求解器成本高从实际经验看如果只是算法题题目没明确要求最优解贪心通常能拿比较可观的分数如果是工程系统我更建议用贪心作为初始解再叠加一轮局部搜索性价比最高。5.3 工程中怎么用贪心三种实用改进第一种是多次随机化贪心。排序时遇到密度相同的物品固定顺序会带来偏差可以随机打乱这些平局物品的顺序运行多次取最好结果。代价只是多几次循环收获往往不小。第二种是贪心后的局部搜索。得到一个贪心解之后检查是否有这样的机会把一个背包里价值较低的物品拿出来换入另一件当前未装入但价值更高的物品同时保证两个背包都不超容量。这种交换操作每做一次总价值就提高一次代码也不复杂。实际项目里这个“贪心初解交换优化”的组合比单纯贪心质量高得多。第三种是两轮分配。第一轮先把密度高的物品按贪心思路放第二轮把剩余物品按体积从小到大重新放一遍。这种策略适合物品重量范围特别大的场景能减少碎片空间。5.4 经验判断我早年在做一个货运装载的排程系统时背包不是三个而是几十辆车货物也有数千件。最开始就只用贪心生成结果很快但业务方觉得总价值不够高。后来加了局部搜索和随机重启解的质量提升明显通常能跑到接近整数规划求解器的结果耗时却只有几秒。这个经历给我的体会是不要迷信贪心也不要一杆子打死贪心。它最合适的位置是作为“快速初始解生成器”配合一轮局部优化在质量和性能之间取得平衡。如果只是自己写代码练习我建议你把这套代码跑通之后把USE_BEST_FIT切换一下看看同样数据下结果差多少再改一改物品数据感受一下不同数据分布对结果的影响。这种手感比死记理论有用得多。最后说一个容易忽略的点贪心算法的代码即使逻辑再简单也一定要在输出里保留完整的装入明细而不是只输出总价值。我之前排查一个分配异常时就靠“哪个物品进了哪个背包”的日志才定位到是排序比较函数写错导致密度倒排。能看到中间过程比只看最终数字重要得多。