分数背包与贪心方法

分数背包与 0-1 背包只差一句话：物品可以切分。正是这点让贪心从错误变成最优。

有容量 $W$ ，第 $i$ 件物品重量 $w_i$ 、价值 $v_i$ ，可取比例 $x_i\in[0,1]$ ：

\max\sum_i x_iv_i, \qquad \text{s.t. }\sum_i x_iw_i\le W.

1. 贪心规则

计算单位重量价值

\rho_i=\frac{v_i}{w_i}.

按 $\rho_i$ 从大到小排序，依次尽量装入：能整件放下就全取，最后一件放不下时只取剩余容量对应的比例。

sort items by value / weight descending
remaining = W
for item in order:
    take = min(1, remaining / item.weight)
    answer += take * item.value
    remaining -= take * item.weight

排序耗时 $O(n\log n)$ ，扫描 $O(n)$ 。

2. 交换论证

设贪心首先选择单位价值最高的物品 $g$ 。若某个最优方案没有尽可能多取 $g$ ，它一定把部分容量给了单位价值不高于 $g$ 的物品 $j$ 。

从 $j$ 挪出同样重量，换成 $g$ ：总重量不变，总价值不会下降。不断交换，便得到一个同样最优且包含贪心首选的方案。剩余容量又是同型子问题，故贪心可递归成立。

关键在于物品可切分，才能做“同重量交换”。

3. 一个例子

容量 50，物品为

重量	价值	单位价值
10	60	6
20	100	5
30	120	4

先取前两件，占 30、得 160；剩余容量 20，取第三件的 $2/3$ ，再得 80。总价值 240。

若这是 0-1 背包，贪心会取前两件得 160，而最优是后两件得 220。不能把分数背包的证明搬到不可切分场景。

4. 贪心算法需要证明什么

一个标准证明通常包含：

贪心选择性质：存在某个最优解包含当前贪心选择；
最优子结构：做出选择后，剩余部分是规模更小的同类最优问题。

“每一步看起来最好”只是算法直觉，不是正确性证明。交换论证、领先法和割性质都是常见证明工具。

5. 相同单位价值与边界

单位价值相同的物品顺序不影响最优总价值，但具体选取方案可能不同。还需处理：

$W=0$ 时答案为 0；
重量必须为正，否则单位价值无定义；
若价值允许为负，显然不应选负价值物品；
浮点比较可能带来误差，可用交叉乘积 $v_iw_j$ 与 $v_jw_i$ 比较比值。

6. 线性规划视角

分数背包是一个结构极简单的线性规划：按价值密度填满容量。最优解至多有一个物品只取一部分，其余物品都是 0 或 1。这也解释了为何排序后只会在容量耗尽处切一次。