Question

（1）练习

16.2-2

经典的 0-1 背包问题

16.2-3

根据假设 w_1 <= w_2 <= ... <= w_n 并且 v_1 >= v_2 >= ... >= v_n。

贪心选择性质：如果该背包问题有解，则一定存在一个最优解包含物品 1。

证明：给定一个最优解，如果已经包含物品 1，则证明结束。否则用物品 1 替代背包中任何一个物品 i，因为 w_1 <= w_i，所以替换一定是可行的；其次，v_1 >= v_i，所以价值一定不会减小。可见替换后仍然是一个最优解。所以从按物品 1，2，...的顺序加入背包，直到不能加入为止。

16.2-4

设 ai 表示第 i 个加油站一第 i-1 个加油站的距离。

最后一次加满了油是在第 j 个站(j 初始时为 0)

若第 k 个站满足 aj + a|j+1 + …… +ak <= n 且 aj + a|j+1 + …… +a|k+1 > n，那么他应该在第 k 个站处加油

16.2-5

对所有点进行从小到大的排序，然后每次取值最小的点 xi，把区间[xi,xi+1]加入到所求的区间集合中，并把属于区间[xi,xi+1]的点 xj 从点集中除去。

16.2-6

见 算法导论-16.2-6

常规算法：

先求 avgi= vi/wi，按照 avgi 从大到小排序，再贪心选择，时间复杂度为 O(nlgn)

改进：

更一般的情况，不需要排序，例如:如果 a1, a2，a3 是 avgi 最大的三个物品，如果它们的总量和不大于 W，我们是不需要知道它们间的相对顺序的。

O(n) 算法：

选择一个物品作为主元，对所有物品进行 Paitition 操作。将 avg 分为三个集合 G = {ai: avgi< m}, Q = {ai：avgi= m}, P = {ai: avgi> m}。分别对 G, Q, P 中元素求和得 SG, SQ, SP。

1. 如果 W < SG, 则令物体的集合为 O = G，对集合 O 递归进行上述过程。

2. 如果 SG<=W <= SG+SQ，则将集合 G 中的元素都放入包中，并将集合 Q 总元素尽可能多的放入包中，结束。

3. 如果 SG+SQ < W, 将 G，Q 中元素放入包中。令物体集合 O = P，总重 W = W - SG - SQ。递归进行上述过程。

16.2-7

对集合 A 和 B 进行排序，每次取最大值，计算 a^b