分类：
2008-09-18 11:05:28
《算法分析与设计》
1．考虑 而不是xi∈{0，1}的连续背包问题。一种可行的贪婪策略是：按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其装入；否则，往背包内装如此物品的一部分。
(a) 对于n=3，w=[100,10,10]，p=[20,15,15]，以及c=105，上述装入法获得结果是什么？
(b)证明这种贪婪算法总能获得最优解。
(c) 用伪代码描述此算法。
2．1）证明当且仅当二分图没有覆盖时，下述算法找不到覆盖。
m＝0; //当前覆盖的大小
对于A中的所有i，New[i]=Degree[i]
对于B中的所有i，Cov[i]=false
while(对于A中的某些i，New[i]>0) {
设v是具有最大的New[i]的顶点；C[m++]=v;
for(所有邻接于v的顶点j) {
If(!Cov[j]) {
Cov[j] = true;
对于所有邻接于j的顶点，使其New[k]减1
}}}
if (有些顶点未被覆盖) 失败
else 找到一个覆盖2）给出一个具有覆盖的二分图，使得上述算法找不到最小覆盖。
3．对于二分图覆盖问题设计另一种贪婪启发算法，贪婪准则是：如果B中某一个顶
点被A中一个顶点覆盖，选择A中这个顶点；否则，从A中选择一个顶点，使得它所
覆盖的未被覆盖的顶点数目最多。给出这种贪婪算法的伪代码。
4．有n个硬币，其中1个是假币，且假币较轻。请用分而治之方法设计一个找出假币的算法。
用伪代码描述你的算法；
用C程序描述你的算法；
分析你的算法的时间复杂性。
5．如果上题中的条件“假币较轻”改为“假币和真币”的重量不同。请用分而治之方法设计一个找出假币的算法，用C程序实现你的算法。
用分而治之算法计算3456*5678；
2）假设两个大整数都是n=2k位，请用伪代码描述两个大整数乘积的分而治之算法。
7．设计一个分而治之算法来计算二叉树中分支结点的个数。请用伪代码描述你的算法。请分析算法的时间复杂度。
8．货物装箱问题：设有一艘货船装货箱。共有n=6件货箱，它们的重量如下表示：[w1,..., w6] = [100, 200, 50, 90, 50, 20]，船的限载重量是c=300。试用贪婪算法装船，要求货箱装得最多。贪婪准则：从剩下的货箱中选择重量最小的货箱。
请给出问题的解；
对一般的n，重量为w=[w1,..., wn]，船的限载重量是c>0，要求船的货箱装得最多，请用伪代码描述你的算法；
考虑有两条船的情况，即有两条船，船的限载重量是分别是c1和c2；共n件货箱，重量为w=[w1,..., wn]，试用贪婪算法装船，要求两条船的货箱装得最多。请描述你的算法，该算法总能产生最优解吗？请说明你的理由。
9． 1）在8（1）的条件下，10． 如果货箱具有价值，11． [p1,..., p6] = [20, 50, 25, 15, 20, 10]。试设计一个装船的贪婪算法，12． 要求装船的货箱的价值最大。
2）对一般的n，价值p=[p1,..., pn]，重量为w=[w1,..., wn]，船的限载重量是c>0，请用伪代码描述你设计的贪婪装船算法，要求装船的货箱的价值最大。
二、习题（15、16、17章）
定义0/1/2背包问题为： 。限制条件为： ，且 ，f(i , y)表示剩余容量为y，剩余物品为：i，i+1，…，n时的最优解的值。
1） 推出f(i , y)的递推表达式（类似于15-1和5-2式）；
2） 请设计求解f(i , y)的算法，3） 并用伪代码描述你的算法；
4） 分析你的算法的复5） 杂性。
6） 设W=[10,20,15,30,10]，7） P=[6,10,15,18,5],c=78，8） 请用你的算法求解。
设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当
2）对n个矩阵连乘积，用伪代码描述你的算法。
对0/1背包问题：n=4，w=[20，25，15，35]，p=[40，49，25，60]，c=62。
1)、画出0/1背包问题的解空间树；
2)、对该树运用回溯算法，写出依回溯算法遍历节点的顺序表及节点。确定回溯算法未遍历的节点。
5．旅行商问题：给出一个n个顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。任何一个包含所有n个顶点的环路被称作一个旅行。在旅行商问题中，要设法找到一条最小耗费的旅行。
1）对图示的例，画出旅行商问题的解空间树；
2）对该树运用回溯算法，写出依回溯算法遍历节点的顺序表及节点。确定回溯算法未遍历的节点。
子集和问题：对于集合S={1，2，5，6，8}，求子集，要求该子集的元素之和d=9。
a) 画出子集和问题的解空间树；
b) 对该树运用回溯算法，c) 写出依回溯算法遍历节点的顺序表及节点。确定回溯算法未遍历的节点；
d) 如果S中有n个元素，e) 指f) 定d，g) 用伪代码写出求解子集和问题的回溯算法。
7．对0/1背包问题：n=4，w=[20，25，15，35]，p=[40，49，25，60]，c=62。
1)、画出0/1背包问题的解空间树；
2)、描述用FIFO分枝定界法解决上述问题的过程；
3）、描述用最大收益分枝定界法解决上述问题的过程。
4）、对一般的n，用伪代码描述0/1背包问题的最大收益分枝定界法。
8．对子集和问题：对于集合S={1，2，5，6，8}，求子集，要求该子集的元素之和d=9。
1)、画出子集和问题的解空间树；
2)、描述用FIFO分枝定界法解决上述问题的过程；
3)、如果S中有n个元素，指定d，用伪代码描述求解子集和问题的FIFO分枝定界法。
9． 旅行商问题：给出一个n个顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。任何一个包含所有n个顶点的环路被称作一个旅行。在旅行商问题中，要设法找到一条最小耗费的旅行。
1）对图示的例，画出旅行商问题的解空间树。
2）描述用FIFO分枝定界法解决上述问题的过程；
3）对有n个顶点的网络，用伪代码描述求解旅行商问题的FIFO分枝定界法。
