Vince Jiang

CSCI3160 / 作业与题解 · 本站更新

CSCI3160 Exercise 3：贪心选择与交换证明

课程：CSCI3160 本组：Regular Exercise Set 3，Problem 1–5；题目（本地课件） p.1；官方答案（本地课件） p.1–3 定位：把“直觉上应该这样选”变成交换证明；用反例识别不可靠的贪心规则。 前后：List 2 · List 4

本文按原题顺序作中文学习解析，题意为概述，完整英文见原件。推导和标明的补充例子为本解析所作。活动区间按本组官方实现视为闭区间：端点相碰也冲突，兼容条件是后一个开始时间严格大于前一个结束时间。目标是选取数量最多的互不相交区间，而非总时长最大。

Problem 1：选最早结束的活动后，剩余问题为何仍能最优（题目 p.1；答案 p.1）

题意。 区间已按结束时间非递减排列。取第一个区间 I，令 S′ 为所有与 I 不相交的区间。已知 T′ 是 S′ 的最优选择，证明加上 I 就是原问题的最优选择。

先补上官方引用的交换论证

“最早结束”为什么可以先选？取原问题任意最优解 O，设 J 是 O 中第一个结束的区间。如果 I 不在 O 中，用 I 替换 J。由于 I 的结束时间不晚于 J，O 中剩余活动的开始时间仍然晚于 I 的结束时间，替换后的集合依旧可行，数量也不变。因此，存在一个含 I 的最优解。

这不意味着每一个最优解都含 I，也不要求最优解唯一。例如若两个活动结束时间相同且互相重叠，选哪一个都可能最优；我们只需证明至少一个最优解与当前贪心选择相容。

再证明剩余部分可以独立优化

取上述含 I 的最优解 O。去掉 I 后，O 的所有剩余区间都与 I 不相交，所以它们属于 S′；它们之间本来就互不相交，因此是 S′ 的一个可行解。因为 T′ 是 S′ 中最优的，便有

∣T′∣≥∣O∣−1. \lvert T'\rvert\ge\lvert O\rvert-1.

另一方面，T′ 中每个区间都与 I 兼容，故它们加 I 是原问题的可行解，其数量至少为 O 的数量。O 已经最优，可行解不可能更多，所以最终数量恰好相等。

这个证明有两个独立环节：贪心选择安全保证可先选 I；最优子结构保证剩下的 S′ 可以重新求最优。只证明第二点不足以支持随意选一个区间。

算一遍（自取例子）

区间为 [1,3]、[2,5]、[4,6]、[7,8]。先选最早结束的 [1,3]；兼容集合为 [4,6]、[7,8]，两者也相容，得到三个活动。如果先选 [2,5]，则会同时挡住前两个可选位置，说明“选谁都可以再求剩余最优”是错误推理。

边界。 S′ 为空时，T′ 为空，加 I 得到一个活动，证明仍成立。空输入没有 I，单独返回空集合即可。

Problem 2：怎样实现而不重复删数组（题目 p.1；答案 p.1）

题意。 将课堂活动选择算法实现为总时间 O(nlog⁡n)O(n\log n)。

一个排序加一次扫描

若输入为空：返回空集合
按结束时间从小到大排序全部区间
答案 T ← 空集合；lastFinish ← 负无穷
依次读区间 [s,f]：
    若 s > lastFinish：
        把该区间加入 T
        lastFinish ← f
返回 T

lastFinish 是最后选中活动的结束时间。已选区间的结束时间递增，因此若新活动在这个时间之后开始，就必然与更早选中的所有活动也不冲突。只需要检查最后一个，无需逐个比较。

为什么跳过的区间以后也不必回头看

若当前区间满足 s≤lastFinishs\le\text{lastFinish}，它与已经确定选择的最后一个区间相交；后续不会撤销这个选择，所以它已经不可能进入本次贪心解。若兼容，则它是尚未处理的候选中结束最早者，Q1 保证可以安全选入。不断应用 Q1，最终得到最优解。

对 Q1 的四区间例子，扫描动作是：选 [1,3]，跳过 [2,5]，选 [4,6]，选 [7,8]。没有实际从数组删除任何元素，却实现了“排除所有冲突活动”的效果。

排序 O(nlog⁡n)O(n\log n)，扫描 O(n)O(n)，总时间 O(nlog⁡n)O(n\log n)；答案存储至多 O(n)O(n)。若输入已按结束时间有序，只需线性扫描。排序的额外空间取决于采用的排序实现。

易错点。 每次找最早结束者时重新扫描全部剩余活动，或每次在数组中物理删除冲突区间，都可能把实现写成平方时间。本题闭区间用 >，不能直接套用另一种允许端点相接的活动模型中的 >=。

Problem 3：最早开始为何不可靠（题目 p.1；答案 p.1）

题意。 某算法每次选开始最早的活动，再删除所有与之重叠的活动。证明它不保证最大活动数。

用官方反例：[1,10]、[2,3]、[4,5]。开始时间分别为 1、2、4，第一步被迫选择 [1,10]。这个长区间覆盖另外两个，删除后已无候选，输出数量为 1。

但 [2,3] 和 [4,5] 互不相交，可以同时选择，数量为 2。它们已经最优：包含长区间最多选 1 个，不含长区间最多从剩下两个中选 2 个。因此错误算法得到 1，最优得到 2，反例成立。

反例不需要很大，也不需要展示算法每次都错。一个合法输入上严格次优，就足以否定“对所有输入保证最优”。这里开始最早的区间唯一，不依赖平局如何处理。

直觉。 开始早并不意味着给后面的活动留得多；真正限制后续空间的是结束时间。长活动可能早早开始，却占用整段可安排多个活动的时间。

Problem 4：冲突最少的活动也不一定安全（题目 p.1；答案 p.1–2）

题意。 每次选与当前集合中其他活动重叠数最少的区间，删除它和所有冲突区间。证明仍可能次优。

将官方的九区间反例展开

用字母标识原答案给出的区间，重叠数不包括自身：

标记 区间 与其重叠的其他区间 数量
A [1,10] B、C 2
B [2,22] A、C、D 3
C [3,23] A、B、D 3
D [20,30] B、C、E 3
E [25,45] D、F 2
F [40,50] E、G、H 3
G [47,62] F、H、I 3
H [48,63] F、G、I 3
I [60,70] G、H 2

首步最小重叠数是 2，候选 A、E、I。需要区分“存在一种平局处理会失败”和“所有平局处理都会失败”；下面分别核对，官方文字对这两种说法混淆了。

若先选 E

E 删除 D、F。剩下左侧 A、B、C 三个两两相交的区间，以及右侧 G、H、I 三个两两相交的区间。每侧最多选一个，而且两侧彼此无冲突，因此算法最终恰好选 3 个：E 加左侧一个加右侧一个。

若先选 A

A 删除 B、C。剩 D、E、F、G、H、I。此时 D 只与 E 冲突，重叠数 1；E、F、I 的重叠数为 2，G、H 为 3。所以算法下一步被迫选择 D，删除 E。之后 F、G、H、I 中，F 和 I 各冲突两个，G 和 H 各冲突三个；先选 F 或 I 均会删除 G、H，但保留另一个。所以最终选择 A、D、F、I，共 4 个。

重要核对：官方答案的强断言不成立。 官方称算法会返回 3 个且必含 E，但按实际重叠计数，以上“先选 A”的合法平局处理会返回 4 个。先选 I 则左右对称，也能返回 4 个。因此原反例能否直接否定“保证最优”，取决于算法是否规定平局规则：未规定时，选 E 是一个合法的失败执行，已足以说明所述规则本身不能保证最优；但不能说它在这个例子上必然失败。

一个不依赖平局的补强反例（本解析构造）

在原集合中再加两个区间 J=[1,9] 和 K=[61,70]。J 与 A、B、C 重叠；K 与 G、H、I 重叠。这样 A 和 I 的冲突数从 2 上升到 3，J 和 K 的冲突数也是 3，而 E 仍只与 D、F 冲突，数量为 2。其他区间的冲突数不会下降。因此 E 成为唯一冲突最少的区间，算法第一步必须选 E。

删除 D、F 后，左侧 A、B、C、J 两两相交，右侧 G、H、I、K 两两相交。算法最多也恰好从每侧选一个，总计 3 个。另一方面，A、D、F、I 仍互不相交，可选 4 个。因此算法严格次优，完全不依赖平局。

如果要确认最优恰好是 4，可把全部区间分成四个两两冲突的组：{A,B,C,J}、{D,E}、{F,G,H}、{I,K}。每组最多选一个，总数至多 4，而上面的四区间方案达到 4。

为什么“冲突少”仍会被骗。 冲突个数把所有邻居算成同等重要，却没有考虑这些邻居之间能否同时入选。E 只挡住 D、F 两个，但这两个可以同时存在于一个好的方案中；A 旁边的许多邻居彼此冲突，本来就不可能全选。局部删除数量不是全局最优损失。

Problem 5：分数背包的价值密度贪心（题目 p.1；答案 p.2–3）

题意。 物品 i 有正重量 wiw_i、正价值 viv_i，可取重量 xix_i，满足 0≤xi≤wi0\le x_i\le w_i，总重量不超过容量 W；所得价值按取用比例计算，最大化总价值。

题目只写了 W 不超过总重量；作为背包容量，还需要 W≥0W\ge0，否则没有可行解。下文按通常容量约定 0≤W≤∑iwi0\le W\le\sum_iw_i 处理。这里 xix_i 是“取了多少重量”，不是比例；比例是 xi/wix_i/w_i。

为什么排序依据是单位重量价值

定义价值密度 di=vi/wid_i=v_i/w_i。取重量 xix_i 的价值为 dixid_ix_i。同样增加一单位重量，密度越高越划算，因此按密度非递增排序，优先装满前面的物品。

按 d[i]=v[i]/w[i] 非递增排序，同时保存原物品编号
remain ← W
依次处理排序后的物品 i：
    x[i] ← min(w[i], remain)
    remain ← remain - x[i]
按原编号输出各 x[i]

不要在证明中把原容量 W 与不断减少的剩余容量混成同一个变量。remain 变为 0 后，后续取用量全为 0。

数值演算（自取例子）

三个物品的 (重量,价值) 为 (10,60)、(20,100)、(30,120)，容量 50。密度分别为 6、5、4。先取第一件全部 10，剩 40；再取第二件全部 20，剩 20；最后取第三件重量 20，即其三分之二。总价值

10⋅6+20⋅5+20⋅4=240. 10\cdot6+20\cdot5+20\cdot4=240.

若按总价值优先，先取第三件 30，再取第二件 20，只得到 220。要比较的是相同重量下的收益，而不是整件总价值。

交换证明：逐个位置把某个最优解变成贪心解

首先，所有密度均为正且物品总重量不少于 W，所以最优解一定用满容量。若尚有空位，则必有物品未取完，增加一点该物品就能严格提高价值，矛盾。

设贪心解为 x，任取一个最优解 y。若二者不同，取最早不同的位置 t。此前的取用量完全相同，因此它们在位置 t 面对相同剩余容量。贪心已经取了允许的最大量，所以 xt>ytx_t>y_t。令 Δ=xt−yt>0\Delta=x_t-y_t>0。

最优解也用满 W，所以它在 t 后面的取用总量足够移出 Δ\Delta。具体地，设共同的前缀总重量为 P，则

∑i>tyi=W−P−yt≥xt−yt=Δ, \sum_{i>t}y_i=W-P-y_t\ge x_t-y_t=\Delta,

其中不等式使用 P+xt≤WP+x_t\le W。从后面若干物品合计拿掉重量 Δ\Delta，转移到物品 t。设各自移出量为 δi≥0\delta_i\ge0，总和为 Δ\Delta。价值变化为

Δdt−∑i>tδidi=∑i>tδi(dt−di)≥0. \Delta d_t-\sum_{i>t}\delta_i d_i =\sum_{i>t}\delta_i(d_t-d_i)\ge0.

最后一个不等式来自密度排序。重量不变，各物品取用量仍合法，价值不下降，所以修改后仍最优，而且与贪心一致的前缀更长。有限次重复后，整个最优解变成贪心解，因此贪心最优。

为什么不能照搬到 0/1 背包。 上面允许把物品拆出任意小重量。若每件只能全拿或不拿，这个交换可能不可行。例如不能为了补齐 2 单位空位而切开一件重 5 的不可分物品。交换证明失败的具体位置就是“任意转移重量”这一步。

补充：用数值追踪一次交换，别只读最后的不等号。 沿前述三物品例子，若某候选把第三件多装2单位，却只装第一件8单位，可把第三件的2单位移回第一件：容量仍50，第一件没有超过重量10，第三件取用减少仍非负；价值增加 2(6−4)=42(6-4)=4。这一步保持可行性，才允许用价值比较改进最优解。若换成不可分物品，所描述的转移根本不是合法动作，即使算出来更大也不能用于证明。

自测：固定密度排序后，为什么贪心不会比某个可行解在“第一个不同位置”拿得更少？

此前前缀完全一样，因此剩余容量相同；贪心取 min(该物品重量,剩余容量)，已经是该位置的合法最大取量。任何可行解在此前不变时都不可能取更多。这个方向先确定，后面的Δ才保证为正，不能先假定想要的交换方向。

排序 O(nlog⁡n)O(n\log n)，填充 O(n)O(n)，总时间 O(nlog⁡n)O(n\log n)。密度相同任意排序仍正确，因为交换价值变化为零。若容量为 0，所有取用量为 0。

本讲核心考点

  • Q1：先证明存在一个兼容贪心选择的最优解，再证明剩余问题最优性。
  • Q2：按结束时间排序，闭区间使用严格兼容判断。
  • Q3：单个合法反例即可否定普遍保证。
  • Q4：反例必须写清平局；原官方例子的“必然失败”说法需要修正。
  • Q5：密度排序与可分割交换，注意容量与剩余容量的区别。

来源与证据

  • 官方题目 p.1；官方答案 p.1–3，2026-09-30 下载。
  • Q4 九区间来自官方答案；十一区间补强反例为本解析构造，已枚举核对最优值和贪心结果。
  • 考试证据：本次仅核对官方练习与答案，未据此断言考试范围。