尧图网页设计 
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 Problem是贪心算法章节中最经典的入门案例之一它允许将一个物品切分后按比例装入背包从而使得每次优先选取单位价值最高的物品这一直觉式策略可以被证明为全局最优。本文将基于 Hello Algo原文档 fractional_knapsack_problem.md系统讲解该问题的数学定义、贪心策略的推导、Python/Java/C/C/Go 等多语言实现、复杂度结论以及完整的反证法正确性证明并给出仓库中的源码与测试文件作为可运行验证依据。读完本文你将能独立完成给定物品重量/价值与背包容量求最大可装载总价值这类问题的贪心建模与实现并理解为何按单位价值贪心在此处必然成立。1. 问题定义物品允许按比例切分!!! question 分数背包问题给定 $n$ 个物品第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$另有一个容量为 $cap$ 的背包。每个物品**只能被选取一次但允许只选取其中的一部分**且被选取部分的价值与其重量成正比。在不超过背包容量的约束下能装入背包的最大总价值是多少下图给出了一个直观的示例数据与最优解在容量为 $50$ 的前提下放入重量为 $20$、价值为 $120$ 的完整物品再放入重量为 $40$ 的物品的 $30/40$即 $\frac{30}{40} \times 210 157.5$得到最大总价值 $120 157.5 277.5$。1.1 与 0-1 背包问题的异同分数背包问题与 0-1 背包问题整体非常相似两者的状态都可以用当前物品 $i$与背包剩余容量 $c$来描述优化目标都是在背包容量的限制下最大化总价值。关于 0-1 背包的完整讨论可参考同仓库 动态规划章节的 0-1 背包问题文档。二者唯一但关键的区别在于物品是否可分割0-1 背包每个物品要么整体装入、要么整体放弃不存在装入一半的选项因此决策是离散的往往需要动态规划求解分数背包允许任意切分物品且装入重量为 $w$ 的部分所带来的价值等于 $w \times val[i-1] / wgt[i-1]$。正是可分割这个特性让局部贪心决策有了通向全局最优的数学保证见第 5 节证明也使分数背包成为少数几个能用贪心算法直接求得精确最优解的问题之一。1.2 单位价值问题分析的核心概念在开始设计策略之前先明确两个基本事实与 greedy_algorithm.md 提出的贪心三步骤中的第一步问题分析对应对物品 $i$ 而言其单位价值unit value即单位重量能带来的价值为 $val[i-1] / wgt[i-1]$若将物品 $i$ 中重量为 $w$ 的部分装入背包则背包新增的价值为 $w \times val[i-1] / wgt[i-1]$与 $w$ 成正比。由于价值 重量 × 单位价值在重量预算固定的约束下显然应优先把预算花在单位价值更高的物品上。这构成了后续贪心策略的直觉起点。2. 贪心策略的推导每次选取单位价值最高的物品背包中总价值的最大化本质上等价于优先装入单位价值更高的物品。由此可归纳出如下贪心策略对应贪心求解步骤中的确定贪心策略排序将所有物品按单位价值 $val[i-1] / wgt[i-1]$ 从高到低排序迭代依次遍历全部物品每一轮都贪心地选取当前单位价值最高的物品切分收尾若遍历到某件物品时背包剩余容量已不足则只装入当前物品的一部分把背包装满随即结束。与硬币找零等贪心可能失效的问题不同可对比 greedy_algorithm.md 中 $coins [1, 20, 50]$ 与 $[1, 49, 50]$ 的反例分数背包问题中可分割的性质恰好使贪心选择能严密成立具体论证见第 5 节。3. 代码实现先定义 Item 再排序 单次遍历仓库在en/codes/下为每种支持语言都提供了本问题的完整实现与驱动代码。核心思路是先定义一个包含重量与价值两个属性的Item对象使物品能够按单位价值排序随后在排序结果上做一次贪心遍历背包装满即停止并返回结果。3.1 Python 实现Python 实现en/codes/python/chapter_greedy/fractional_knapsack.py 代码非常精简class Item: Item def __init__(self, w: int, v: int): self.w w # Item weight self.v v # Item value def fractional_knapsack(wgt: list[int], val: list[int], cap: int) - int: Fractional knapsack: Greedy algorithm # Create item list with two attributes: weight, value items [Item(w, v) for w, v in zip(wgt, val)] # Sort by unit value item.v / item.w from high to low items.sort(keylambda item: item.v / item.w, reverseTrue) # Loop for greedy selection res 0 for item in items: if item.w cap: # If remaining capacity is sufficient, put the entire current item into the knapsack res item.v cap - item.w else: # If remaining capacity is insufficient, put part of the current item into the knapsack res (item.v / item.w) * cap # No remaining capacity, so break out of the loop break return res该文件末尾还附带了可直接运行的驱动代码取wgt [10, 20, 30, 40, 50]、val [50, 120, 150, 210, 240]、cap 50运行后打印最大可装载价值。手动推演一遍该用例可验证算法逻辑各物品单位价值分别为 $5, 6, 5, 5.25, 4.8$排序后先整体装入重量 20 / 价值 120 的物品剩余容量 30下一件重量为 40 的物品只能装入 $\frac{30}{40}$贡献 $210 \times \frac{30}{40} 157.5$总价值恰为 $277.5$。3.2 Java 实现Java 实现en/codes/java/chapter_greedy/fractional_knapsack.java 通过自定义Item类与比较器完成排序算法主体逻辑与 Python 版完全一致/* Fractional knapsack: Greedy algorithm */ static double fractionalKnapsack(int[] wgt, int[] val, int cap) { // Create item list with two attributes: weight, value Item[] items new Item[wgt.length]; for (int i 0; i wgt.length; i) { items[i] new Item(wgt[i], val[i]); } // Sort by unit value item.v / item.w from high to low Arrays.sort(items, Comparator.comparingDouble(item - -((double) item.v / item.w))); // Loop for greedy selection double res 0; for (Item item : items) { if (item.w cap) { // If remaining capacity is sufficient, put the entire current item into the knapsack res item.v; cap - item.w; } else { // If remaining capacity is insufficient, put part of the current item into the knapsack res (double) item.v / item.w * cap; // No remaining capacity, so break out of the loop break; } } return res; }注意由于最终结果可能不是整数Java 等语言中的函数返回值被声明为double比较器中也需先将除法转换为浮点运算避免整数除法截断导致排序错误。3.3 其他语言的关键差异仓库还在en/codes/下提供了 C、C、C#、Go、JavaScript、TypeScript、Dart、Kotlin、Rust、Ruby、Swift 等实现均可作为对照参考C 实现使用std::sort配合 lambda 比较器(double)a.v / a.w (double)b.v / b.w降序排列C 实现定义typedef struct { int w; int v; } Item;通过qsort与比较函数sortByValueDensity按价值密度排序需注意比较时同样要转成浮点数同时用手动malloc管理物品数组并用free释放Go 实现借助sort.Slice与闭包比较器完成降序排序且配套了单元测试文件 fractional_knapsack_test.go可在该语言目录下直接以go test方式运行验证。无论是哪种语言构造 Item → 按单位价值降序排序 → 单次贪心遍历的骨架始终保持一致差异仅体现在排序 API 与对象定义语法上。4. 复杂度分析结合 Python 实现 的代码结构可以清晰地拆分各部分开销时间复杂度$O(n \log n)$。开销主要来自排序编程语言内置排序算法通常耗时 $O(n \log n)$。而在排序之外最坏情况下需要遍历整个物品列表即 $O(n)$其中 $n$ 为物品数量。因此总体时间复杂度为 $O(n \log n)$相较 $O(n \times cap)$ 级别的动态规划方案在常规数据规模下更具优势。空间复杂度$O(n)$。由于需要初始化一个包含全部物品的Item对象列表额外空间随物品数量线性增长即 $O(n)$。排序过程本身的栈空间复杂度通常为 $O(\log n)$ 或 $O(n)$视具体语言的排序实现而定但不改变整体的 $O(n)$ 量级结论。5. 正确性证明反证法论证贪心选择性质局部贪心 全局最优并非对所有问题都成立因此需要严格证明。本仓库文档采用反证法论证过程如下构造假设设物品 $x$ 具有最高的单位价值假设某个算法得到了一个最优值res但该最优解中并没有包含物品 $x$。执行替换从背包中的任意一件物品上取出一个单位重量再放入来自物品 $x$ 的一个单位重量。导出矛盾由于 $x$ 的单位价值最高替换后背包的总价值必然严格大于原来的res。这与res是最优解的前提相矛盾因此任何最优解都必然包含物品 $x$。归纳推广对解中其余物品逐一构造同样的矛盾可推得单位价值更高的物品永远是更优的选择从而证明该贪心策略有效。这一证明的本质是交换论证在可分割的前提下任何装入低单位价值物品的方案都能被替换为高单位价值物品的方案严格改进所以贪心解与最优解之间不存在差距。6. 几何直观把问题看作在重量轴上圈出最大面积反证法给出了严格结论而从几何视角也能直观地理解贪心策略为何奏效若将物品的重量视作二维图表的横轴、单位价值视作纵轴那么分数背包问题可以被理解为在横轴上的有界区间内圈出最大包围面积——每个物品对应一块宽度为 $wgt$、高度为单位价值的矩形而背包容量的限制相当于横轴上的一个总宽度上限。在此图景下贪心策略先取单位价值最高柱状图最高的物品就等价于优先占领高度最大的区域切分收尾则相当于最后一个物品只占满剩余宽度。由于同一高度内单位面积的价值恒定无论从几何还是代数角度贪心都能取得最大面积——这与第 5 节的证明结论相互印证。7. 小结适合用贪心求解的典型场景分数背包问题是 greedy_algorithm.md 中列举的典型贪心问题之一。由本问题的经验可以归纳贪心算法的适用条件当问题同时具备贪心选择性质局部最优总能通向全局最优与最优子结构时贪心通常是最佳选择——因为它的代码通常比回溯与动态规划更简洁、运行更高效。而一旦问题不允许分割如 0-1 背包贪心的前提即被破坏就需要转向动态规划等精确方法。读者可进一步深入同一仓库中的 贪心算法综述greedy_algorithm.md 了解硬币找零等贪心失效的案例与反证/归纳等证明工具并通过 本章习题 与 本章小结 巩固理解若想对比 0-1 背包的动态规划解法请参阅 0-1 背包问题文档。所有文中涉及的源码均可直接在仓库en/codes/对应语言目录下编译运行或执行测试验证。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello Algo 算法精讲：分数背包问题的贪心解法——单位价值策略、代码实现与正确性证明
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 Problem是贪心算法章节中最经典的入门案例之一它允许将一个物品切分后按比例装入背包从而使得每次优先选取单位价值最高的物品这一直觉式策略可以被证明为全局最优。本文将基于 Hello Algo原文档 fractional_knapsack_problem.md系统讲解该问题的数学定义、贪心策略的推导、Python/Java/C/C/Go 等多语言实现、复杂度结论以及完整的反证法正确性证明并给出仓库中的源码与测试文件作为可运行验证依据。读完本文你将能独立完成给定物品重量/价值与背包容量求最大可装载总价值这类问题的贪心建模与实现并理解为何按单位价值贪心在此处必然成立。1. 问题定义物品允许按比例切分!!! question 分数背包问题给定 $n$ 个物品第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$另有一个容量为 $cap$ 的背包。每个物品**只能被选取一次但允许只选取其中的一部分**且被选取部分的价值与其重量成正比。在不超过背包容量的约束下能装入背包的最大总价值是多少下图给出了一个直观的示例数据与最优解在容量为 $50$ 的前提下放入重量为 $20$、价值为 $120$ 的完整物品再放入重量为 $40$ 的物品的 $30/40$即 $\frac{30}{40} \times 210 157.5$得到最大总价值 $120 157.5 277.5$。1.1 与 0-1 背包问题的异同分数背包问题与 0-1 背包问题整体非常相似两者的状态都可以用当前物品 $i$与背包剩余容量 $c$来描述优化目标都是在背包容量的限制下最大化总价值。关于 0-1 背包的完整讨论可参考同仓库 动态规划章节的 0-1 背包问题文档。二者唯一但关键的区别在于物品是否可分割0-1 背包每个物品要么整体装入、要么整体放弃不存在装入一半的选项因此决策是离散的往往需要动态规划求解分数背包允许任意切分物品且装入重量为 $w$ 的部分所带来的价值等于 $w \times val[i-1] / wgt[i-1]$。正是可分割这个特性让局部贪心决策有了通向全局最优的数学保证见第 5 节证明也使分数背包成为少数几个能用贪心算法直接求得精确最优解的问题之一。1.2 单位价值问题分析的核心概念在开始设计策略之前先明确两个基本事实与 greedy_algorithm.md 提出的贪心三步骤中的第一步问题分析对应对物品 $i$ 而言其单位价值unit value即单位重量能带来的价值为 $val[i-1] / wgt[i-1]$若将物品 $i$ 中重量为 $w$ 的部分装入背包则背包新增的价值为 $w \times val[i-1] / wgt[i-1]$与 $w$ 成正比。由于价值 重量 × 单位价值在重量预算固定的约束下显然应优先把预算花在单位价值更高的物品上。这构成了后续贪心策略的直觉起点。2. 贪心策略的推导每次选取单位价值最高的物品背包中总价值的最大化本质上等价于优先装入单位价值更高的物品。由此可归纳出如下贪心策略对应贪心求解步骤中的确定贪心策略排序将所有物品按单位价值 $val[i-1] / wgt[i-1]$ 从高到低排序迭代依次遍历全部物品每一轮都贪心地选取当前单位价值最高的物品切分收尾若遍历到某件物品时背包剩余容量已不足则只装入当前物品的一部分把背包装满随即结束。与硬币找零等贪心可能失效的问题不同可对比 greedy_algorithm.md 中 $coins [1, 20, 50]$ 与 $[1, 49, 50]$ 的反例分数背包问题中可分割的性质恰好使贪心选择能严密成立具体论证见第 5 节。3. 代码实现先定义 Item 再排序 单次遍历仓库在en/codes/下为每种支持语言都提供了本问题的完整实现与驱动代码。核心思路是先定义一个包含重量与价值两个属性的Item对象使物品能够按单位价值排序随后在排序结果上做一次贪心遍历背包装满即停止并返回结果。3.1 Python 实现Python 实现en/codes/python/chapter_greedy/fractional_knapsack.py 代码非常精简class Item: Item def __init__(self, w: int, v: int): self.w w # Item weight self.v v # Item value def fractional_knapsack(wgt: list[int], val: list[int], cap: int) - int: Fractional knapsack: Greedy algorithm # Create item list with two attributes: weight, value items [Item(w, v) for w, v in zip(wgt, val)] # Sort by unit value item.v / item.w from high to low items.sort(keylambda item: item.v / item.w, reverseTrue) # Loop for greedy selection res 0 for item in items: if item.w cap: # If remaining capacity is sufficient, put the entire current item into the knapsack res item.v cap - item.w else: # If remaining capacity is insufficient, put part of the current item into the knapsack res (item.v / item.w) * cap # No remaining capacity, so break out of the loop break return res该文件末尾还附带了可直接运行的驱动代码取wgt [10, 20, 30, 40, 50]、val [50, 120, 150, 210, 240]、cap 50运行后打印最大可装载价值。手动推演一遍该用例可验证算法逻辑各物品单位价值分别为 $5, 6, 5, 5.25, 4.8$排序后先整体装入重量 20 / 价值 120 的物品剩余容量 30下一件重量为 40 的物品只能装入 $\frac{30}{40}$贡献 $210 \times \frac{30}{40} 157.5$总价值恰为 $277.5$。3.2 Java 实现Java 实现en/codes/java/chapter_greedy/fractional_knapsack.java 通过自定义Item类与比较器完成排序算法主体逻辑与 Python 版完全一致/* Fractional knapsack: Greedy algorithm */ static double fractionalKnapsack(int[] wgt, int[] val, int cap) { // Create item list with two attributes: weight, value Item[] items new Item[wgt.length]; for (int i 0; i wgt.length; i) { items[i] new Item(wgt[i], val[i]); } // Sort by unit value item.v / item.w from high to low Arrays.sort(items, Comparator.comparingDouble(item - -((double) item.v / item.w))); // Loop for greedy selection double res 0; for (Item item : items) { if (item.w cap) { // If remaining capacity is sufficient, put the entire current item into the knapsack res item.v; cap - item.w; } else { // If remaining capacity is insufficient, put part of the current item into the knapsack res (double) item.v / item.w * cap; // No remaining capacity, so break out of the loop break; } } return res; }注意由于最终结果可能不是整数Java 等语言中的函数返回值被声明为double比较器中也需先将除法转换为浮点运算避免整数除法截断导致排序错误。3.3 其他语言的关键差异仓库还在en/codes/下提供了 C、C、C#、Go、JavaScript、TypeScript、Dart、Kotlin、Rust、Ruby、Swift 等实现均可作为对照参考C 实现使用std::sort配合 lambda 比较器(double)a.v / a.w (double)b.v / b.w降序排列C 实现定义typedef struct { int w; int v; } Item;通过qsort与比较函数sortByValueDensity按价值密度排序需注意比较时同样要转成浮点数同时用手动malloc管理物品数组并用free释放Go 实现借助sort.Slice与闭包比较器完成降序排序且配套了单元测试文件 fractional_knapsack_test.go可在该语言目录下直接以go test方式运行验证。无论是哪种语言构造 Item → 按单位价值降序排序 → 单次贪心遍历的骨架始终保持一致差异仅体现在排序 API 与对象定义语法上。4. 复杂度分析结合 Python 实现 的代码结构可以清晰地拆分各部分开销时间复杂度$O(n \log n)$。开销主要来自排序编程语言内置排序算法通常耗时 $O(n \log n)$。而在排序之外最坏情况下需要遍历整个物品列表即 $O(n)$其中 $n$ 为物品数量。因此总体时间复杂度为 $O(n \log n)$相较 $O(n \times cap)$ 级别的动态规划方案在常规数据规模下更具优势。空间复杂度$O(n)$。由于需要初始化一个包含全部物品的Item对象列表额外空间随物品数量线性增长即 $O(n)$。排序过程本身的栈空间复杂度通常为 $O(\log n)$ 或 $O(n)$视具体语言的排序实现而定但不改变整体的 $O(n)$ 量级结论。5. 正确性证明反证法论证贪心选择性质局部贪心 全局最优并非对所有问题都成立因此需要严格证明。本仓库文档采用反证法论证过程如下构造假设设物品 $x$ 具有最高的单位价值假设某个算法得到了一个最优值res但该最优解中并没有包含物品 $x$。执行替换从背包中的任意一件物品上取出一个单位重量再放入来自物品 $x$ 的一个单位重量。导出矛盾由于 $x$ 的单位价值最高替换后背包的总价值必然严格大于原来的res。这与res是最优解的前提相矛盾因此任何最优解都必然包含物品 $x$。归纳推广对解中其余物品逐一构造同样的矛盾可推得单位价值更高的物品永远是更优的选择从而证明该贪心策略有效。这一证明的本质是交换论证在可分割的前提下任何装入低单位价值物品的方案都能被替换为高单位价值物品的方案严格改进所以贪心解与最优解之间不存在差距。6. 几何直观把问题看作在重量轴上圈出最大面积反证法给出了严格结论而从几何视角也能直观地理解贪心策略为何奏效若将物品的重量视作二维图表的横轴、单位价值视作纵轴那么分数背包问题可以被理解为在横轴上的有界区间内圈出最大包围面积——每个物品对应一块宽度为 $wgt$、高度为单位价值的矩形而背包容量的限制相当于横轴上的一个总宽度上限。在此图景下贪心策略先取单位价值最高柱状图最高的物品就等价于优先占领高度最大的区域切分收尾则相当于最后一个物品只占满剩余宽度。由于同一高度内单位面积的价值恒定无论从几何还是代数角度贪心都能取得最大面积——这与第 5 节的证明结论相互印证。7. 小结适合用贪心求解的典型场景分数背包问题是 greedy_algorithm.md 中列举的典型贪心问题之一。由本问题的经验可以归纳贪心算法的适用条件当问题同时具备贪心选择性质局部最优总能通向全局最优与最优子结构时贪心通常是最佳选择——因为它的代码通常比回溯与动态规划更简洁、运行更高效。而一旦问题不允许分割如 0-1 背包贪心的前提即被破坏就需要转向动态规划等精确方法。读者可进一步深入同一仓库中的 贪心算法综述greedy_algorithm.md 了解硬币找零等贪心失效的案例与反证/归纳等证明工具并通过 本章习题 与 本章小结 巩固理解若想对比 0-1 背包的动态规划解法请参阅 0-1 背包问题文档。所有文中涉及的源码均可直接在仓库en/codes/对应语言目录下编译运行或执行测试验证。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考