CSCI3160 Special 3：活动选择与背包反例

原件：Sp03 题目（本地课件） p.1；原 PDF 标题写作 CSCI3610。 每题先题解后解析；反例为自行推导。活动按闭区间处理。

Problem 1：运行最早结束活动选择

题解

输出 {[1,10],[20,30],[40,50],[60,70]}，共4个活动。

具体解析

原九区间已按结束时间排列。先选[1,10]，跳过开始时间2、3的[2,22]、[3,23]；接着选[20,30]，跳过[25,45]；选[40,50]，跳过[47,62]、[48,63]；最后选[60,70]。每次新开始严格大于上次结束，所以四个互相兼容。

为什么最优？将任意最优方案最早结束的活动替换成当前最早结束者，不会妨碍后续活动；因此可以把某个最优方案逐步交换成上述贪心选择。这里使用的是“最早结束”，不是Regular3 Q4的“冲突最少”，同一输入在不同规则下输出可不同。

Problem 2：最短活动优先不保证最优

题解

反例取A=[0,4]、B=[5,9]、C=[3,6]。C长度3，唯一最短；A、B各长度4。算法先选C，删除A、B，得到1个；最优选择A、B，得到2个。

具体解析

C横跨两个彼此分离的好活动：它与A交于[3,4]，与B交于[5,6]，但A结束4早于B开始5，所以A、B可同时选。只有3个区间，若包含C只能选1个，不含C可选2个，所以最优恰好2。没有长度平局，也没有端点相碰的歧义。

最短只控制单个区间占用的时长，不能保证它坐落的位置不会同时破坏两个安排。反例说明普遍保证不成立，不要求每个输入都失败。

Problem 3：分数背包按总价值排序会失败

题解

两物品 (重量,价值) 为(10,100)、(1,99)，容量W=1。按价值顺序先取第一件的1单位重量，价值10；改取第二件全部重量，价值99，故原算法不是最优。

具体解析

第一件总价值100确实高于99，符合原题给定顺序；但它单位重量价值只有10，第二件有99。两种方案都只占1单位，后者更好，严格反例成立。容量不超过总重量11，也满足题面条件。

分数背包可切割，因此比较的是单位资源收益v/w。只按v排序忽略了实现这个总价值需要多少重量。正确密度贪心及交换证明见Regular3；本题的任务只需给出合法的失败实例。

Problem 4：0/1背包按价值排序也会失败

题解

容量W=4，三块金砖 (重量,价值) 为(4,5)、(2,3)、(2,3)，已按价值非增排序。算法选第一块便用满，价值5；最优选后两块，总重量4、价值6。

具体解析

不能将第一块切开，因为是0/1选择。算法扫描时第二、三块均因剩余容量0被跳过。所有可行方案中，第一块不能与任何其他块共存；后两块可以共存，且正价值使取两个优于只取一个，故6为确切最优。

这个反例否定“按整件价值优先”，但也不能由分数背包正确性推出“按价值密度就能解决0/1背包”：不可分割时交换小部分重量的证明失效。学习反例时必须核对对象可否分割、容量条件和排序规则，不能把两种背包当成同一问题。

改成密度优先仍不能救回 0/1 背包。 下面是补充反例，区别于 Q4 原题的按价值规则：容量 4，物品 (重量,价值) 为 (3,5),(2,3),(2,3)。密度 $5/3>3/2$，所以密度优先先拿第一件，剩余容量 1，所得 5；后两件合起来重量 4、价值 6。分数背包的交换证明会把一小份重量从低密度物品移到高密度物品，但 0/1 约束禁止只换其中一份。缺失的是交换后的可行性，不能只复述“单位重量更值钱”。

来源与证据

官方题目p.1；Q1使用原题九区间，Q2–Q4为本文构造的严格反例，无官方答案可对照。