算法设计与分析王晓东

设所给的输入为W>0，wi>1,vi>0,1≤i≤n。不妨设0≤w1≤w2≤..≤wn。由题意知v1≥v2≥..≥vn>0。由此可知vi/wi≥vi+1/wi+1，1≤i≤n-1. 贪心选择性质： 当w1>W时问题无解。

当w1≤W时，存在0-1背包问题的一个最优解S包含｛1,2,..,n｝使得1∈S。

事实上，设S包含｛1,2,..,n｝使0-1背包问题的一个最优解，且1不∈S。对任意i∈S，取Si=S∪{1}-{i}，则Si满足贪心选择性质的最优解。 习题5-2 Fibonacci序列的Huffman编码

试证明：若n个字符的频率恰好是前n个Fibonacci数，用贪心法得到它们的Huffman编码树一定为一棵“偏斜树”。

证明：n个字符的频率恰好是前n个Fibonacci数，则相应的哈夫曼编码树自底向上第i个内结点中的数为k=0∑if(k)。用数学归纳法容易证明k=0∑ifkk=1 ∑ i fk + fi+1= k=1 ∑ i+1 fk， 说明对i+3上述结论成立.

该性质保证了频率恰好是前n个Fibonacci数的哈夫曼编码树具有“偏斜树”形状。

习题5-3 记 T为图G= (V, E) 的最小生成树，同时设顶点集合A包含V，设 (u, v) ∈E 为连接A 和 V–A的权重最小的边，证明：必有(u, v) ∈T. 证明：

用反证法。因为T为图G= (V, E) 的最小生成树，在连接A 和 V–A的边中至少有一条属于T中。假设(u, v) 不属于T，则必有(u?, v?) 属于T, 这里(u?, v?) 也是连接A 和 V–A的边, 且 (u?, v?)的权重大于(u, v) 的权重. 若将T中的(u?, v?)换成(u, v)得到T?, 显然T?也是G的一个生成树。但由于(u?, v?)的权重大于(u, v) 的权重，可知T的权重大于T? 的权重，这与” T为图G= (V, E) 的最小生成树” 矛盾。

习题5-4 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 分析与解答：

设所给的n个活动为1，2，…，n，它们的开始时间和结束时间分别为s[i]和f[i]，i=1~n，且f[1]

可以将n个活动1，2，…，n看作实直线上的n个半闭活动区间(s[i],f[i],i=1~n)。所讨论的问题实际上是求这n个半闭区间的最大重叠数。因为重叠的活动区间所相应的活动是互不相容的。若这n个活动区间的最大重叠数为m，则这m个重叠区间所对应的活动互不相容，因此至少安排m个会场来容纳这m个活动。

为了有效地对这n个活动进行安排，首先将n个活动区间的2n个端点排序。然后，用扫描算法，从左到右扫描整个实直线。在每个事件点处（即活动的开始时刻或结束时刻）作会场安排。当遇到一个开始时刻s[i]，就将活动i安排在一个空闲的会场中。遇到一个结束时候f[i]，就将活动i占用的会场释放到空闲会场栈中，以备使用。经过这样一遍扫描后，最多安排了m个会场（m是最大重叠区间数）。因此所作的会场安排是最优的。上述算法所需的计算时间主要用于对2n个区间端点的排序，这需要O(nlogn)计算时间。 具体算法描述如下。

public static int greedy(point []x) {

int sum=0, curr=0, n=x.length; MergeSort.mergeSort(x);

for (int i=0; i

//处理x[i]=x[i+1]的情况

if (( i == n-1∣∣x[i].compareTo(x[i+1])<0)&& curr>sum) sum=curr; }

return sum; }

习题5-5 假设要在m个会场里安排一批活动，并希望使用尽可能多地安排活动。设计一个有效的贪心算法进行安排。

Algorithm greedy(s,f,m,n); Input s[1:n], f[1:n]; Output x[1:m, 1:n]; Begin

对数组s和f中的2n个元素排序存入数组y[1:2n]中； 空闲栈清空；d数组所有元素置初值0； For i=1 to 2n do Begin

If 元素y[i] 原属于s then If 空闲栈不空then

取出栈顶场地j; d[j]=d[j]+1; y[i] 存入x[j, d[j] ]; If 元素y[i] 原属于f then

设其相应的s 存于x[j,k] 中，将j存入空闲栈中； End For i= 1 to m do For j=1 to d[j] do Output x[i,j]; End

习题5-6 删数问题 问题描述

给定n位正整数a，去掉其中任意个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。 分析与解答：

贪心策略：最近下降点优先。 public static void delek(String a) {

int i,m=a.length();

if ( k>= m) {System.out.println(0); return;} while (k>0) {

for (i=0; (i

while (a.length()>1 && a.charAt(0)==?0?) a=a.Remove(0,1); System.out.println(a); }

第六章 回溯法 习题6-1 子集和问题

子集和问题的一个实例 。其中， 是一个正整数的集合，sum是一个正整数。子集和问题判定是否存在A的一个子集A1，使得 。

试设计一个解子集和问题的回溯法。 分析与解答：

设计解子集和问题的回溯法如下。 Algorithm subset-sum begin

For j=1 to n do Begin

sp=0; t=sum; i=j; finish=false; repeat

if t>=a[i] then begin

sp=sp+1；s[sp]=i; t=t-a[i]; if t=0 then i=n; end; i=i+1; while i>n do if sp>1 then begin

if t=0 then out; t=t+a[s[sp]]; i=s[sp]+1; sp=sp-1 end else

begin finish=true; i=1 end until finish end end

习题6-2 中国象棋的半个棋盘如图所示，马自左下角往右上角跳。规定只许向右跳，不许向左跳，计算所有的行走路线。 Algorithm chess Begin

top=0; y0=0; x0=0; di=1; r=0; push; repeat pop;

while di<=4 do begin

g=x0+x[di]; h=y0+y[di]; if (g=8) and (h=4) then out

else begin di=di+1；push; x0=g; y0=h; di=1 end end until empty end

algorithm push begin

top=top+1；sx[top]=x0; sy[top]=y0; d[top]=di; end algorithm pop begin

x0=sx[top]; y0=sy[top]; di =d[top]; top=top－1； end

习题6-3. 在n个连成排的方格内填入R或B，但相邻连个方格内不能都填R。计算所有可能的填法。 R B B R B

Algorithm Red-Black; Begin

For i=1 to n do b[i]=0; T=1; Repeat

b[t]=b[t]+1 ; if b[t]>2 then {回溯} begin b[t]=0 ; t=t-1 ; end else begin

if b[t]=2 then a[t]= ?B? else if a[t-1]=?R? then t=t-1 else a[t]=?R?;

if t=n then output a else t=t+1 end until t=0

第七章 分支限界法

习题7-2. 写出用分支界限法求解下面的重排九宫问题的算法。 解答：

我们对九宫中的位置做如下的编号： 位置编号 1 2 3