hello-algo 分数背包问题：贪心策略、代码实现与正确性证明

教程文档示例工程教育【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址https://gitcode.com/GitHub_Trending/he/hello-algo点击查看免费下载分数背包Fractional Knapsack是《Hello 算法》贪心章节中最适合入门贪心思想的经典优化问题与 0-1 背包不同它允许将物品切分后按重量比例装取价值从而让“每轮选择单位价值最高的物品”这一贪心策略天然成立。本文以仓库中的 Python 代码 为骨架逐行拆解算法实现并补充复杂度分析、反证法正确性证明、多语言实现对照与运行验证方式帮助你完整掌握这一贪心算法范式。问题定义允许切分的背包给定 $n$ 个物品第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$以及一个容量为 $cap$ 的背包。每个物品只能选择一次但可以选择物品的一部分价值根据选择的重量比例计算问在限定背包容量下背包中物品的最大价值。下图给出了仓库文档中使用的示例数据在该示例中5 个物品的重量与价值分别为 $wgt [10, 20, 30, 40, 50]$、$val [50, 120, 150, 210, 240]$背包容量 $cap 50$。完整问题描述可参见 docs/chapter_greedy/fractional_knapsack_problem.md。与 0-1 背包问题的区别分数背包问题和 0-1 背包问题整体上非常相似状态都包含当前物品 $i$ 和剩余容量 $c$目标都是求限定背包容量下的最大价值。关键不同点在于本题允许只选择物品的一部分——可以对物品任意切分并按照重量比例计算相应价值对于物品 $i$它在单位重量下的价值为 $val[i-1] / wgt[i-1]$简称单位价值value density也称性价比假设放入一部分物品 $i$重量为 $w$则背包增加的价值为 $w \times val[i-1] / wgt[i-1]$。正是“可切分”这一性质让分数背包拥有了与 0-1 背包截然不同的求解路径0-1 背包需要动态规划在“取 / 不取”之间做权衡而分数背包可以直接向单位价值最高的物品“敞口装取”直至背包装满。贪心策略按单位价值从高到低选取最大化背包内物品总价值本质上是最大化单位重量下的物品价值。由此可以推理出分数背包的贪心策略共三步将物品按照单位价值从高到低进行排序遍历所有物品每轮贪心地选择单位价值最高的物品若剩余背包容量不足则使用当前物品的一部分填满背包。从图中可以看到先取单位价值最高6.0的 20kg / 120 元物品再取单位价值次高5.25的 40kg / 210 元物品但此时剩余容量只剩 30kg不足以整件装入于是按比例只装入 30kg 的部分获得 $210 \times 30 / 40 157.5$ 的价值最终总价值为 $120 157.5 277.5$。代码实现与逐行解析仓库中该算法的 Python 实现位于 codes/python/chapter_greedy/fractional_knapsack.py同时 codes/pythontutor/chapter_greedy/fractional_knapsack.md 内嵌了这段代码的逐行可视化执行链接可配合学习class Item: 物品 def __init__(self, w: int, v: int): self.w w # 物品重量 self.v v # 物品价值 def fractional_knapsack(wgt: list[int], val: list[int], cap: int) - int: 分数背包贪心 # 创建物品列表包含两个属性重量、价值 items [Item(w, v) for w, v in zip(wgt, val)] # 按照单位价值 item.v / item.w 从高到低进行排序 items.sort(keylambda item: item.v / item.w, reverseTrue) # 循环贪心选择 res 0 for item in items: if item.w cap: # 若剩余容量充足则将当前物品整个装进背包 res item.v cap - item.w else: # 若剩余容量不足则将当前物品的一部分装进背包 res (item.v / item.w) * cap # 已无剩余容量因此跳出循环 break return res Driver Code if __name__ __main__: wgt [10, 20, 30, 40, 50] val [50, 120, 150, 210, 240] cap 50 n len(wgt) # 贪心算法 res fractional_knapsack(wgt, val, cap) print(f不超过背包容量的最大物品价值为 {res})逐段理解这段代码物品建模定义Item类封装重量w与价值v两个属性这是为了后续排序时能同时携带重量与价值信息避免索引错位构造物品列表zip(wgt, val)将重量数组与价值数组按位置配对列表推导式一次性生成全部Item对象核心贪心排序items.sort(keylambda item: item.v / item.w, reverseTrue)以单位价值为键降序排序将性价比最高的物品排在最前。这一步是贪心策略的直接体现循环装取遍历排序后的物品若item.w cap说明剩余容量充足整件装入并累加价值、扣减容量否则只装入剩余容量对应的一部分价值(item.v / item.w) * cap并立即break——因为背包装满后不可能再放入任何物品结果返回累加值res即为限定容量下的最大物品价值。运行上述 Driver Code控制台将输出不超过背包容量的最大物品价值为 277.5复杂度分析对代码进行复杂度拆解排序阶段内置排序算法的时间复杂度通常为 $O(n \log n)$其中 $n$ 为物品数量贪心遍历阶段除排序之外最差情况下需要遍历整个物品列表因此时间复杂度为 $O(n)$综合时间复杂度$O(n \log n)$主导项来自排序空间复杂度由于初始化了一个Item对象列表需要 $O(n)$ 的额外空间排序本身的辅助空间为 $O(\log n)$ 或 $O(n)$取决于具体语言实现但物品列表的 $O(n)$ 已是主导项。作为对比贪心算法章节总览 指出相比动态规划贪心算法通常拥有更低的时间复杂度这正是它的核心优势之一。正确性证明反证法与几何直觉贪心策略是否真的能得到最优解这需要严谨证明仓库文档给出了基于反证法的经典证明思路假设物品 $x$ 是单位价值最高的物品某个算法求得的最大价值为res但该解中不包含物品 $x$现在从背包中拿出单位重量的任意物品并替换为单位重量的物品 $x$。由于物品 $x$ 的单位价值最高替换后的总价值一定大于res这与“res是最优解”矛盾说明最优解中必须包含物品 $x$对于解中的其他物品也可以构建出同样的矛盾。总而言之单位价值更大的物品总是更优选择贪心策略由此被证明有效。此外docs/chapter_greedy/fractional_knapsack_problem.md 还给出了一个直观的几何类比将物品重量和物品单位价值分别看作二维图表的横轴与纵轴则分数背包问题可转化为“求在有限横轴区间下围成的最大面积”从几何角度看单位价值即柱状高度贪心策略等价于“每次取最高的柱”而可切分性保证每次都能把柱取到横轴区间耗尽为止——这从直观上解释了为何该策略不会“浪费”容量这也是它区别于 0-1 背包柱不可切分、可能取不到最优的本质原因。多语言实现对照仓库在 codes 目录下为分数背包提供了 13 种语言的实现各语言在“构造物品 按单位价值排序 贪心装取”的主干上完全一致差异主要体现在语法细节上语言实现文件排序方式返回类型Pythonfractional_knapsack.pylist.sort(keylambda item: item.v / item.w, reverseTrue)int累加后自动转为 floatCfractional_knapsack.cqsort 单位价值比较函数floatCfractional_knapsack.cppsort lambda 比较器doubleJavafractional_knapsack.javaArrays.sortComparator.comparingDoubledoubleGofractional_knapsack.gosort.Slice 闭包比较float64JavaScriptfractional_knapsack.jsArray.sort((a, b) b.v / b.w - a.v / a.w)numberTypeScriptfractional_knapsack.ts同 JavaScript带类型标注numberC#fractional_knapsack.csArray.Sort 比较器doubleSwiftfractional_knapsack.swiftitems.sort 闭包DoubleKotlinfractional_knapsack.ktitems.sortBy 取负单位价值DoubleRustfractional_knapsack.rssort_bypartial_cmpf64Dartfractional_knapsack.dartitems.sortcompareTodoubleRubyfractional_knapsack.rbitems.sort! 宇宙飞船运算符Integer/Float几个值得注意的语言特性C 语言使用qsort与结构体数组比较函数中通过(float)(t1-v) / t1-w (float)(t2-v) / t2-w判定密度大小并在循环结束后显式free(items)释放堆内存Rust因浮点数未实现Ord需用partial_cmp(...).unwrap()完成比较Go在 fractional_knapsack_test.go 中提供了TestFractionalKnapsack单元测试直接验证贪心结果C#的实现将算法封装为FractionalKnapsack实例方法并以[Test]标注的Test()方法驱动运行与项目的测试框架衔接。运行与验证方式你可以按以下方式在本地运行这些实现进行验证Python直接执行python3 fractional_knapsack.py输出“不超过背包容量的最大物品价值为 277.5”Ccodes/c/chapter_greedy/CMakeLists.txt中已声明add_executable(fractional_knapsack fractional_knapsack.c)可通过 CMake 构建后运行输出格式为%0.2f即277.50Go在codes/go目录下执行go test通过 测试文件 验证结果其他语言各文件均自带 Driver Code /main入口Swift 使用main枚举、Rust 使用fn main可直接编译运行。无论使用哪种语言只要贪心排序与装取逻辑一致得到的最大价值都应为 277.5——这与数学推导完全吻合可作为自检基准。小结分数背包问题清晰展示了贪心算法的完整解题范式分析问题特性可切分→ 确定贪心策略按单位价值降序装取→ 证明正确性反证法。通过仓库提供的 Python 逐行代码、PythonTutor 可视化、13 种语言实现与配套测试你可以快速上手并验证这一经典算法。在掌握分数背包之后不妨继续阅读 贪心算法章节总览 与 章节小结进一步理解贪心选择性质与最优子结构以及零钱兑换、最大容量、最大切分乘积等其他贪心经典问题。赞分享教程文档示例工程教育【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址https://gitcode.com/GitHub_Trending/he/hello-algo点击查看免费下载相关推荐Hello 算法中的分数背包问题单位价值贪心策略的原理、实现与正确性证明Hello 算法中的分数背包问题单位价值贪心策略的原理、实现与正确性证明 本篇技术指南聚焦《Hello 算法》中分数背包问题Fractional Knaps教程文档示例工程教育Hello Algo 贪心算法章节总复习贪心选择性质、三步解题框架与三大经典贪心问题的正确性证明Hello Algo 贪心算法章节总复习贪心选择性质、三步解题框架与三大经典贪心问题的正确性证明 本文是对《Hello 算法》本仓库英文文档树 en/doc教程文档示例工程教育Hello 算法最大容量问题详解双指针贪心策略的推导、实现与正确性证明Hello 算法最大容量问题详解双指针贪心策略的推导、实现与正确性证明 在《Hello 算法》hello algo的贪心算法章节中最大容量问题是一个教程文档示例工程教育上一篇Salt 内核参数管理实战深入解析 salt.modules.linux_sysctl 执行模块下一篇阿里云Qwen3-Coder震撼开源4800亿参数重构AI编程生产力SWE-Bench评分比肩Claude4创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考