数据结构与算法 / 系统课时
分数背包问题
分数背包问题
给定容量有限的背包和一组可拆分物品,本课将用“单位重量价值最高者优先”的贪心策略求出最大收益,并通过可运行代码说明它为何适用于分数背包,却不能直接替代零一背包的动态规划解法。
学习目标
- 能够按价值密度排序并实现分数背包算法。
- 能够解释贪心选择成立的交换论证。
- 能够区分分数背包与零一背包的问题结构和求解方法。
核心思路与执行过程
物品可以只取一部分,因此每件物品的关键指标是价值密度 。算法先按 从高到低排序,再依次装入:剩余容量足够时整件取走,不足时只取恰好填满背包的比例。

这一策略正确的核心是交换论证:若某个方案先占用了低密度物品的重量,同时还存在未装入的高密度物品,就可以交换等量重量,使总价值不下降。不断交换后,总能得到按密度从高到低装入的最优方案。
完整可运行示例
下面的 Java 17 程序先排序,再根据剩余容量计算每件物品的选取比例。将代码保存为 FractionalKnapsackDemo.java。
java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Locale;
public class FractionalKnapsackDemo {
record Item(String name, double weight, double value) {
double density() {
return value / weight;
}
}
public static void main(String[] args) {
List<Item> items = new ArrayList<>(List.of(
new Item("A", 10, 60),
new Item("B", 20, 100),
new Item("C", 30, 120)
));
items.sort(Comparator.comparingDouble(Item::density).reversed());
double remainingCapacity = 50;
double totalValue = 0;
for (Item item : items) {
if (remainingCapacity <= 0) {
break;
}
// 只取当前物品能够装入背包的比例。
double fraction = Math.min(1.0, remainingCapacity / item.weight());
double gainedValue = item.value() * fraction;
totalValue += gainedValue;
remainingCapacity -= item.weight() * fraction;
System.out.printf(
Locale.ROOT,
"选择 %s,比例 %.2f,获得价值 %.2f%n",
item.name(),
fraction,
gainedValue
);
}
System.out.printf(Locale.ROOT, "最大总价值:%.2f%n", totalValue);
}
}编译并运行:
bash
javac FractionalKnapsackDemo.java
java FractionalKnapsackDemo预期输出
text
选择 A,比例 1.00,获得价值 60.00
选择 B,比例 1.00,获得价值 100.00
选择 C,比例 0.67,获得价值 80.00
最大总价值:240.00复杂度、边界与零一背包差异
排序耗时为 ,线性扫描耗时为 ,因此总时间复杂度为 。选择阶段只使用常数额外变量;Java 的列表排序可能使用与输入规模相关的辅助空间。
| 对比项 | 分数背包 | 零一背包 |
|---|---|---|
| 物品能否拆分 | 可以取任意比例 | 只能整件取或不取 |
| 密度贪心是否保证最优 | 保证 | 不保证 |
| 常见解法 | 排序加线性扫描 | 动态规划、分支限界 |
| 典型复杂度 | 常见伪多项式复杂度 |
实现时还要检查三个边界:容量不能为负,物品重量必须大于零,价值与重量若使用浮点数,应避免直接用相等比较判断业务条件。零一背包中,局部密度最高的物品可能阻塞更优组合,因此不能照搬本课算法。
本课总结
- 可拆分性使价值密度成为可证明正确的贪心选择标准。
- 算法由“按密度排序”和“按剩余容量取比例”两步组成。
- 分数背包与零一背包的关键差异不在输入形式,而在物品是否允许拆分。
下一课预告
下一课将学习“霍夫曼编码”,继续使用贪心思想反复合并低频节点,并构造平均编码长度最短的前缀码树。
按自己的节奏,确认真正理解。