算法导论15 Problems 答案
15-1
a
1 | COIN-CHANGING-SPECIAL(n) |
在最优情况下，\(25\)分硬币可以由\(2\)个\(10\)分硬币和\(1\)个\(5\)分硬币表示出；类似的，\(10=5\times 2,5=1\times 5\)。
不难证明这个问题满足最优子结构，如果一个拼凑\(n\)分硬币的最优解\(S\)的子集\(S'\)不是拼凑\(m\)分硬币的最优解，那么存在一个最优解\(S''\)是拼凑\(m\)枚硬币的最优解，从而构造出一个拼凑\(n\)分硬币的最优解\((S-S')\cup S''\)，引出了矛盾。因此这个问题满足最优子结构。
不难发现这个问题满足贪心选择性质。在一个最优解中，最终\(10\)分硬币必定最多\(2\)个，\(5\)分硬币最多为\(1\)个。对于每个大面额硬币\(n\)，它总能由多个小面额硬币表示出来。因此如果一个解没有贪心地使用大硬币来表示，那么以这个大硬币额度为子问题的解必定不是最优的。因此满足贪心选择性质。
b
最优子结构的证明过程与问题15-1-a相同。
假设一个最优解为\(S=(s_0,s_1,\dots,s_k)\)。那么\(\forall i < k,s_i< c\)总是成立的。因为如果\(\exists j< k,s_j\ge c\)，那么可以考虑用\(1\)枚价值为\(c^{j+1}\)的硬币代替这\(c\)枚价值为\(c^{j}\)的硬币，从而减少了\(c-1\)枚硬币。
假设一个解\(S'\)没有贪心选择尽可能大的硬币，也就是说，一个超过价值\(c^j\)的子问题却没有用价值为\(c^j\)的硬币拼凑，那么哪怕\(\forall j< i\)，每一种价值为\(c^{j}\)的硬币都使用\(c-1\)个，都只能凑出\((c-1)(c^0+c^1+c^2+\dots+c^{i-1})=c^i-1\)的价值。因此在此情况下，必定存在一个\(j< i,s_j'\ge c\)成立，和最优解成立的条件矛盾。因此这个问题下满足贪心选择性质。
故这个算法的贪心策略是正确的。
c
如果硬币币种为\([1,4,6]\)，需要拼凑的值为\(8\)，那么贪心算法下的解为\([1,1,6]\)，但是最优解为\([4,4]\)。
d
考虑使用动态规划算法来解决本题。这个问题和完全背包问题一样，每种硬币的币值视为物品的“重量”，价值视为\(1\)，区别仅在于这里求的是必定装满重量\(k\)后，价值之和的最小值。
令状态\(f[i, j]\)表示前\(i\)种物品凑出的重量和为\(j\)时，最小的总价值。对于当前状态，第\(i\)种物品有两种决策：取或者是不取。如果不取，那么相当于从状态\(f[i-1,j]\)转移而来；如果取，那么相当于从\(f[i,j-w_i]\)处取一个物品\(i\)转移而来，并且从中择优转移。因此不难写出如下状态转移方程：
\(f[i,j]= \left \{\begin{aligned} &0 & & \text{if}\quad i=0\land j=0 \\ &+\infty & & \text{if}\quad i=0\land j\neq0 \\ &f[i-1,j]& & \text{if} \quad i>0 \land j< w_i\\ &\in\{f[i-1,j],f[i,j-w_i]+1\}& & \text{if} \quad i>0 \land j\ge w_i\\ \end{aligned}\right.\)
因此最终答案为\(f[n,k]\)。
算法CHANGE-PROBLEM给出了具体的实现过程。第2-3行的嵌套循环说明这个算法的时间复杂度为\(O(nk)\)。
1 | CHANGE-PROBLEM(w, n, k) |
15-2
a
将每个任务\(a_i\)按照运行时间升序排序，然后按这个顺序执行每个任务即可。
最优子结构的证明：对于一个最优解\(S\)，完成了\(i\)个任务后，子问题则为剩下的\(n-i\)个任务，如果这\(n-i\)不是按照最优的方式进行的，那么存在一个更优的解\(S'\)进行这\(n-i\)个任务。那么由于两个步骤是独立的，将\(S\)的关于前\(i\)个任务的解和\(S'\)组合就能得出一个比\(S\)更优秀的解\(S''\)，这与\(S\)是最优秀的矛盾。
接下来证明贪心选择性质。
假设任务为\(\{b_1,b_2,\dots,b_n\}\)，那么有\(\displaystyle{C_{b_i}=\sum_{j=1}^i p_{b_j}}\)。平均时间\(\overline{C}\)可以如下计算：
\(\begin{aligned} \overline{C} &= \dfrac{1}{n}\sum_{i=1}^n C_{b_i}\\ &=\dfrac{1}{n} \sum_{i=1}^n\sum_{j=1}^i p_{b_j}\\ &=\dfrac{1}{n}\sum_{j=1}^n(n-j+1) p_{b_j} \end{aligned}\)
令序列\(\{a\}\)为\(a_j=n-j+1,\{c\}\)则是\(p\)的一个置换，可以发现\(a\)是降序的。那么为了最小化\(\overline{C}\)的值，\(\{c\}\)必须是升序的。对于一个解\(S\)，如果\(\exists i< j,c_i>c_j\)成立，那么考虑构造出一个解\(S'\)，它是将解\(S\)中的\(c_i\)与\(c_j\)交换，那么交换前后的平均完成时间的变化为\(\dfrac{1}{n}(a_jb_i+a_ib_j)-\dfrac{1}{n}(a_jb_j+a_ib_i)=-\dfrac{(a_j-a_i)(b_j-b_i)}{n}<0\)。从而说明解\(S''\)比\(S\)更优。由此证明贪心选择性质成立。
因此这个贪心策略是正确的。算法的整个过程主要在于为\(\{p\}\)排序，时间复杂度为\(O(n\lg n)\)。
b
这个贪心算法是，处理器总是优先处理剩余运行时间最短的任务。也就是说，如果当前任务\(a_1\)剩下的运行时间为\(p_1\)，但是随后插入一个运行时间为\(p_2\)的任务\(a_2\)，且\(p_2< p_1\)，那么就挂起任务\(a_1\)去运行\(a_2\)。
考虑如此场景：假设为当前时刻为\(t=r_2\)，任务\(a_1\)正在被执行，剩余时间为\(p_1\)，此时插入一个任务\(a_2\)，剩余时间为\(p_2(p_2< p_1)\)。令决策\(S'\)表示不立刻挂起\(a_1\)，令\(P_t\)表示从\(t\)时刻开始，决策\(S'\)下执行任务\(a_1\)或者是\(a_2\)的时间片，也就是说，\(|P|=p_1+p_2\)。那么可以发现，无论是\(a_1\)后执行完还是\(a_2\)后执行完，并不影响\(P_t\)中的最大值，因此我们需要其中一个任务尽快执行完。那么，只有当\(P_t\)中的前面的一段连续时间片分给\(a_1\)或者是\(a_2\)时，才能够保证这两个任务之一才能执行完，从而保证这两个任务的执行总时间最小化。由于\(p_2<p_1\)，因此将\(P_t\)中的前\(p_2\)个时间片分给\(a_2\)才是最优的。由此构造出决策\(S\)。由于对\(P_t\)中第一个时间片中处理不同，因此\(S\)和\(S'\)是不一样的。因此我们从\(S'\)得到了一个更优秀的\(S\)。因此贪心选择性质成立。
最终，这个算法的贪心策略是正确的。使用最小优先队列维护每个任务的加入和完成时间可以以\(O(n\lg
n)\)的时间复杂度计算出结果。具体过程由算法GEN-SCHEDULE给出。因为使用了最小优先队列，整个过程的时间复杂度为\(O(n\lg n)\)。
1 | // 假设所有任务已经按释放时间r排好序。 |