分数背包问题详解（Java语言贪心算法实现教程）

什么是分数背包问题？

假设你有一个容量为 W 的背包，还有 n 个物品。每个物品都有自己的重量（weight）和价值（value）。在分数背包问题中，你可以取任意比例的某个物品（比如取一半、三分之一等），目标是让装入背包的总价值最大。

例如：

• 背包容量：50
• 物品1：重量 = 10，价值 = 60 → 单位价值 = 6
• 物品2：重量 = 20，价值 = 100 → 单位价值 = 5
• 物品3：重量 = 30，价值 = 120 → 单位价值 = 4

显然，我们应该优先拿单位价值高的物品。这就是贪心算法的核心思想：每一步都做当前看起来最优的选择。

解决思路

1. 计算每个物品的单位价值（价值 ÷ 重量）
2. 按照单位价值从高到低对物品进行排序
3. 依次将物品装入背包：
   • 如果当前物品能完全装下，就全部拿走
   • 如果装不下，就拿一部分（刚好装满背包）

Java 实现代码

下面我们用 Java 编写一个完整的分数背包问题求解程序。为了便于理解，我们将物品封装成一个类，并使用 Arrays.sort() 进行排序。

import java.util.Arrays;import java.util.Comparator;class Item {    double weight;    double value;    double ratio; // 单位价值    public Item(double weight, double value) {        this.weight = weight;        this.value = value;        this.ratio = value / weight;    }}public class FractionalKnapsack {    public static double getMaxValue(Item[] items, double capacity) {        // 按单位价值降序排序        Arrays.sort(items, new Comparator<Item>() {            @Override            public int compare(Item a, Item b) {                return Double.compare(b.ratio, a.ratio);            }        });        double totalValue = 0.0;        for (Item item : items) {            if (capacity >= item.weight) {                // 能全部装下                totalValue += item.value;                capacity -= item.weight;            } else {                // 只能装一部分                totalValue += item.ratio * capacity;                break; // 背包已满            }        }        return totalValue;    }    public static void main(String[] args) {        Item[] items = {            new Item(10, 60),            new Item(20, 100),            new Item(30, 120)        };        double capacity = 50;        double maxValue = getMaxValue(items, capacity);        System.out.println("最大价值为: " + maxValue); // 输出: 240.0    }}

代码解析

• Item 类存储每个物品的重量、价值和单位价值（ratio）。
• 在 getMaxValue 方法中，我们先按单位价值从高到低排序。
• 然后遍历排序后的物品列表，尽可能多地装入高价值物品。
• 当背包剩余空间不足以装下整个物品时，就按比例取一部分，并结束循环。

为什么贪心算法在这里有效？

因为分数背包允许取部分物品，所以局部最优（每次选单位价值最高的）一定能导致全局最优。但请注意：这个策略不适用于0-1背包问题（不能分割物品），那是动态规划的领域。

总结

通过本教程，你已经学会了如何用 Java 实现分数背包问题。关键在于理解贪心算法的思想：总是优先选择性价比最高的物品。这种思路简单高效，时间复杂度主要由排序决定，为 O(n log n)。

希望这篇背包问题教程对你有帮助！如果你正在学习算法或准备面试，掌握这类经典问题将大大提升你的编程能力。快动手试试修改代码，测试不同的输入吧！