数据结构与算法 / 系统课时

分数背包问题

分数背包问题

给定容量有限的背包和一组可拆分物品,本课将用“单位重量价值最高者优先”的贪心策略求出最大收益,并通过可运行代码说明它为何适用于分数背包,却不能直接替代零一背包的动态规划解法。

学习目标

  • 能够按价值密度排序并实现分数背包算法。
  • 能够解释贪心选择成立的交换论证。
  • 能够区分分数背包与零一背包的问题结构和求解方法。

核心思路与执行过程

物品可以只取一部分,因此每件物品的关键指标是价值密度 ri=vi/wir_i = v_i / w_i。算法先按 rir_i 从高到低排序,再依次装入:剩余容量足够时整件取走,不足时只取恰好填满背包的比例。

分数背包按价值密度选择物品的过程

这一策略正确的核心是交换论证:若某个方案先占用了低密度物品的重量,同时还存在未装入的高密度物品,就可以交换等量重量,使总价值不下降。不断交换后,总能得到按密度从高到低装入的最优方案。

完整可运行示例

下面的 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

复杂度、边界与零一背包差异

排序耗时为 O(nlog⁡n)O(n \log n),线性扫描耗时为 O(n)O(n),因此总时间复杂度为 O(nlog⁡n)O(n \log n)。选择阶段只使用常数额外变量;Java 的列表排序可能使用与输入规模相关的辅助空间。

对比项 分数背包 零一背包
物品能否拆分 可以取任意比例 只能整件取或不取
密度贪心是否保证最优 保证 不保证
常见解法 排序加线性扫描 动态规划、分支限界
典型复杂度 O(nlog⁡n)O(n \log n) 常见伪多项式复杂度 O(nC)O(nC)

实现时还要检查三个边界:容量不能为负,物品重量必须大于零,价值与重量若使用浮点数,应避免直接用相等比较判断业务条件。零一背包中,局部密度最高的物品可能阻塞更优组合,因此不能照搬本课算法。

本课总结

  • 可拆分性使价值密度成为可证明正确的贪心选择标准。
  • 算法由“按密度排序”和“按剩余容量取比例”两步组成。
  • 分数背包与零一背包的关键差异不在输入形式,而在物品是否允许拆分。

下一课预告

下一课将学习“霍夫曼编码”,继续使用贪心思想反复合并低频节点,并构造平均编码长度最短的前缀码树。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

分数背包问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通