算法导论35.5 Exercises 答案
35.5-1
首先证明\(P_i\)包含了\(\{x_1,x_2,\dots,x_{i-1},x_i\}\)中所有子集的元素之和。
当\(i=1\)时，\(P_1=\{0,x_1\}\)，也就是包含了空集，以及只有一个元素\(x_1\)的集合的元素之和。
当\(i>1\)时，假设\(P_{i-1}\)包含了\(\{x_1,x_2,\dots,x_{i-1}\}\)中所有子集的元素之和。将\(\{x_1,x_2,\dots,x_{i-1},x_{i}\}\)中的所有子集分成两部分：包含\(x_i\)的和不包含\(x_i\)的。对于不包含\(x_i\)的任何子集，这些子集和将和\(P_{i-1}\)中的和值对应；对于包含\(x_{i}\)的任何子集，只需要将不包含\(x_i\)的任何子集都添加上一个元素\(x_i\)，那么这一部分的子集和将和\(P_{i-1}+x_i\)中的对应。因此，\(P_i=P_{i-1}\cup (P_{i-1}+x_i)\)包含了\(\{x_1,x_2,\dots,x_{i-1},x_i\}\)中所有子集的元素之和，原结论成立。
接下来证明EXACT-SUBSET-SUM的第4行执行结束之后，\(L_i\)是\(P_i\)中不超过\(t\)的有序列表，将采用归纳法进行证明。
当\(i=0\)时，\(L_0=\langle 0\rangle\)，也就是只包含了空集的元素之和，即为\(0\)。
当\(i>0\)时，假设\(L_{i-1}\)包含了\(\{x_1,x_2,\dots,x_{i-1}\}\)中所有子集的元素之和不超过\(t\)的一个有序列表，接下来考虑\(L_i\)。可见，集合\(P_{i-1}-L_{i-1}\)包含的都是大于\(t\)的元素，由于\(x_i> 0\)，因此\((P_{i-1}-L_{i-1})+x_i\)包含的仍然是大于\(t\)的元素，它们必定不会存在于\(L_i\)中。对于\(L_{i-1}\)中的所有元素，加上\(x_i\)后那么就要判断是否超过\(t\)，如果超过了那么就舍去。因此，通过归并时的合并策略，EXACT-SUBSET-SUM的第4行执行结束之后可以得到\(P_i\)中不超过\(t\)的元素的列表，原结论成立。
35.5-2
将使用归纳法进行证明。不失一般性，假设\(x_1,x_2,\dots,x_i\le t\)均成立，否则可以直接抛弃掉\(x_i>t\)的元素，因为它必定不可能在集合中。
当\(i=0\)时，可见\(P_0=\{0\},L_0=\langle 0\rangle\)。原结论必定成立。
当\(i=1\)时，可见\(P_1=\{0,x_1\}\)。由于\(x_1>0\cdot(1+\epsilon/2n),x_1\le t\)，因此\(L_1=\langle0,x_1\rangle\)。对于元素\(x_1\)，有\(x_1/(1+\epsilon/2n)\le x_1\le x_1\)，因此原结论成立。
当\(i>1\)时，假设对于集合\(P_{i-1}\)中所有不超过\(t\)的元素\(y\)，在\(L_{i-1}\)中都存在元素\(z\)使得\(\dfrac{y}{(1+\epsilon/2n)^{i-1}}\le z\le y\)。考虑\(P_i\)中元素的情况。
对于\(P_i\)中的元素，根据等式35.21，它们无非要么来自\(P_{i-1}\)，要么来自\(P_{i-1}+x_i\)。考虑如下两种情况：
考虑\(P_{i-1}\)中的元素，题目中的假设说明了\(P_{i-1}\)中所有不超过\(t\)的所有元素\(y\)，在\(L_{i-1}\)必定存在\(z\)，使得\(\dfrac{y}{(1+\epsilon/2n)^{i-1}}\le z\le y\)。如果\(z\)在\(L_i\)中，那么由于\(\dfrac{y}{(1+\epsilon/2n)^{i}}\le\dfrac{y}{(1+\epsilon/2n)^{i-1}}\le z\le y\)，因此结论成立。如果\(z\)不在\(L_i\)中，那么说明\(z\)在第4行
TRIM的调用过程中被另外一个元素\(z'\)替代了，且\(z'\le \dfrac{z}{1+\epsilon/2n}\)，因此有\(\dfrac{y}{(1+\epsilon/2n)^{i}}=z'\le\dfrac{y}{(1+\epsilon/2n)^{i-1}}\le z\le y\)。那么\(z'\)在\(L_i\)的存在说明\(y\)也满足题目条件，原结论成立。考虑\(P_{i-1}+x_i\)的元素，题目中的假设说明了\(P_{i-1}\)中所有不超过\(t\)的所有元素\(y\)，其中令\(y=y'+x_i\)，那么在\(L_{i-1}\)必定存在\(z'\)，使得
\[\dfrac{y'}{(1+\epsilon/2n)^{i-1}}\le z'\le y'\qquad(1)\]
对不等式\((1)\)中第一项添加\(\dfrac{x_i}{(1+\epsilon/2n)^{i-1}}\)，第二、三项添加\(x_i\)，可见该不等式仍然成立：
\[\dfrac{y'+x_i}{(1+\epsilon/2n)^{i-1}}\le z'+x_i\le y'+x_i\qquad(2)\]
在第3行对MERGE-LISTS调用后，\(L_{i-1}+x_i\)将会产生一个元素\(z=z'+x_i\)，并将其添加到\(L_i\)中。接下来考察\(z\)是否会被第4行TRIM的调用过程中被另外一个元素替代。如果\(z\)没有被替代，那么由不等式\((2)\)可以得到\(\dfrac{y}{(1+\epsilon/2n)^{i-1}}\le z\le
y\)。同样的，可以得到\(\dfrac{y}{(1+\epsilon/2n)^{i}}\le\dfrac{y}{(1+\epsilon/2n)^{i-1}}\le
z\le y\)，因此原结论成立。如果\(z\)被替代了，那么必定是被某个元素\(z''\)替代了，且\(z''\le
\dfrac{z}{1+\epsilon/2n}\)，因此有\(\dfrac{y}{(1+\epsilon/2n)^{i}}=z''\le\dfrac{y}{(1+\epsilon/2n)^{i-1}}\le
z\le y\)。那么\(z''\)在\(L_i\)的存在说明\(y\)也满足题目条件，原结论成立。
最终原结论是成立的。
35.5-3
令\(f(x)=\left(1+\dfrac{\epsilon}{2x}\right)^x\)，考虑\(\dfrac{df(x)}{dx}\)，有
\(\begin{aligned} \ln f(x) &= x\ln \left(1+\dfrac{\epsilon}{2x}\right)\\ \dfrac{d\ln f(x)}{dx} &=\ln \left(1+\dfrac{\epsilon}{2x}\right)- \dfrac{\epsilon}{\epsilon+2x}\\ \dfrac{df(x)}{dx}\cdot\dfrac{1}{f(x)}&=\ln \left(1+\dfrac{\epsilon}{2x}\right)- \dfrac{\epsilon}{\epsilon+2x}\\ \dfrac{df(x)}{dx}&=f(x)\cdot\left(\ln \left(1+\dfrac{\epsilon}{2x}\right)- \dfrac{\epsilon}{\epsilon+2x}\right) \end{aligned}\)
由于\(\epsilon,x>0\)，因此有\(\ln \left(1+\dfrac{\epsilon}{2x}\right)- \dfrac{\epsilon}{\epsilon+2x}\ge \dfrac{\epsilon}{2x}-\dfrac{\epsilon}{\epsilon+2x}>0\)。
由于\(f(x)>0\)，因此\(\dfrac{df(x)}{dx}>0\)，原结论成立。
35.5-4
只需要将整个过程进行的过程求“补”即可，相当于是在删或不删子集中的元素\(x_i\)。在每步的最后迭代中，将小于\(t\)的元素全部删除即可。
修改后的算法由TRIM'和APPROX-SUBSET-SUM'给出。对算法APPROX-SUBSET-SUM'的性能分析和APPROX-SUBSET-SUM完全相同。
1 | TRIM'(L, δ) |
35.5-5
基本思想是，为\(L_i\)中的每个子集和\(s\)添加一个新的数据\(p\)，用于表示它之前是从子集和中\(p\)得到的，也即是说，将某个子集和为\(p\)的某个子集添加了一个元素\(p-s\)，从而达到了子集和\(s\)。
最终取到最大的\(s\)后，访问其对应的\(p\)，并对\(s\)值减去\(p\)，直到最终\(s=0\)时，构造出了一个和为\(z^{\ast}\)的子集。
由于只是多维护了一组数据，因此这个算法和APPROX-SUBSET-SUM是一样的。
具体过程由APPROX-SUBSET-SUM'', TRIM''给出。
1 | TRIM''(L, δ) |