分数背包

分数背包允许拆分物品。按价值密度，即价值÷重量，从高到低装入；遇到第一件装不下的物品，取其中一部分填满剩余容量。可分割、单位价值固定时，密度贪心最优；禁止拆分后，同一规则不再可靠。

把物品画成矩形：宽是重量，高是价值密度，面积是价值。容量是固定宽度的架子。先装高矩形，最后竖切一片，让每单位宽度获得尽可能高的价值。

分数背包如何工作

计算每件的 value / weight，按密度降序。可整件装入就全取，否则取重量 min(weight, remaining)，相应价值按比例计算，填满后停止。发生部分取用后，不再考虑其余物品。

模型假设物品独立、连续可分、重量为正、单位价值恒定。用于可分预算、带宽或货物分配时，要先确认这些条件。存在边际收益变化或不可拆块，就不是这里的矩形模型。

为什么拆分让贪心安全

若已装入部分重量的密度为 d，而尚有可用物品密度 d′ > d，可以用等重的一小片高密度物品换掉低密度部分，价值增加。可分割性保证交换可以只动一小片，不必整件搬走。反复消除这种可改进部分，就得到优先使用最高可用密度的方案。

画布在正式填装前先演示：用最高密度的一片替换最低密度的等宽一片，增加的面积就是收益。

0/1 背包不能任意交换碎片。密度较高的整件可能留下无法利用的空隙，局部选择影响之后能否装下别的物品。第二幕禁止拆分，对照同一密度规则与真正的整件最优解。

逐步演示

默认容量 50，物品按“价值/重量”给出：A = 120/30，B = 60/10，C = 45/15，D = 100/20。

1. 密度：A 为 4.0，B 为 6.0，C 为 3.0，D 为 5.0。A 的总价值最高，密度却只排第三。
2. 排序：B、D、A、C。
3. 交换检验：先放 C 的 10 单位重量，价值 30；换为等重 B，价值变 60。相同宽度增加 10 × (6.0 − 3.0) = 30。
4. 全取 B：重量 10 ≤ 剩余 50，累计价值 60，剩余 40。
5. 全取 D：重量 20 ≤ 剩余 40，累计价值 160，剩余 20。
6. 切 A：重 30，剩余只有 20，取 min(30, 20) = 20，即三分之二。增加 120 × 20/30 = 80，总价值 240，剩余 0。
7. 停止：C 未被考虑，分数方案为 240。
8. 禁止拆分：撤回 A 切片。整件 A 放不进 20 的空隙，跳过它，继续取整件 C，密度贪心总值 205。
9. 整件最优对照：枚举四件物品的全部 16 种选择，A+D 恰重 50，价值 220。不可拆贪心 205 小于 0/1 最优 220，两者又小于分数最优 240。相较不可拆贪心，一次切割增加 35。

画布的切线对齐剩余容量末端，切片与原矩形等高，因为密度不变。结尾用等比例柱比较 205、220、240。

时间与空间复杂度

总时间 O(n log n)。有序列表及排序工作区之外，扫描只需 O(1) 状态；保存物品与输出本身仍占空间。每次至多排序一次、扫描一次。

经典 0/1 背包的容量 DP 为 O(n·W)，属于伪多项式；其一般精确优化是 NP-hard 问题，不能把分数贪心推广为整件问题的多项式精确算法。

边界情况

• 全放得下：总重不超过容量时，无需切割，三种方案总值一致。All items fit 展示可分割性没有额外收益的情况。
• 第一件就太宽：容量低于最高密度物品重量，第一件取分数后即停止。First item cut 从重 30 的物品取 20。
• 恰好放下：min(weight, remaining) = weight，整件装入，不应画成切割。
• 密度相等：任一同值顺序都给相同总值，本课保留输入顺序。Equal densities 展示这种等价。
• 分数结果：默认 2/3 × 120 = 80 恰为整数；若从价值 100、重 30 的物品取重 20，结果为循环小数。显示保留一位小数。

常见错误

• 按总价值排序。 默认先取 A 会用 30 容量获得密度 4，留下更高密度 B；该顺序得到 220，而不是 240。
• 把规则搬到 0/1。 默认不可拆密度贪心 205，整件最优 220。重量组合不能由密度排序概括。
• 部分重量收费按整件价值。 应算 value × take/weight；矩形只保留部分宽度，面积也按比例减少。
• 容量为 0 后还继续装。 第一处部分切割已填满，必须停止，最多只有一件取分数。
• 浮点密度比较不谨慎。 可用 v1 × w2 与 v2 × w1 交叉比较，在乘积精确且不溢出的范围内避免除法误差；本课使用这种方法保持排序确定。