算法试题

(1) 简述算法复杂性分析的方法及用途。

答：算法复杂性分析的方法有解析法和实验测量法，分析的角度分为时间复杂度和空间复杂度。

用途：根据算法复杂度分析的结果选择适当的算法，或评价算法 例如，选择满足空间要求的算法，选择有一定时间要求的算法等。

(2) 算法A的计算时间f(n)满足递归关系式：f(n)=2f(n-1)+1; n>0,f(0)-1. 算法B的计算时间

g (n)=2f(n/2)+logn. 请使用渐进符号分别表示f(n)和g(n) 答： f(n)=O(2^n) G(n)=O(n)

(3) 简述多项式约化的含义，并简述证明一个问题是NPC问题的步骤（6分）。 解：问题P 可多项式地约化为问题Q ,如果存在一个有多项式界的确定性算法T,使得：

（1）对每个输入字符串x, T产生一字符串T(x).

（2）x是P的合法输入且P对x有yes答案当且仅当T(x) 是Q的合法输入且有yes答案

证明问题Q是NP-完全问题的步骤： （1） 选择一已知的NP-完全问题P （2） 证明P可多项式的约化为 Q

2. （7分） 分析下面用伪代码描述的算法的复杂性，写出分析过程。 for m = 2 to n do{ for i = 0 to n-m do{ j = i + m

w(i, j) = w(i, j-1) + P(i) + Q(j)

c(i, j)= mini}

}

W(n,n)，P(n)，Q(n)，c(n,n)为算法中使用的数组并已初始化

答：mini3n

3. 给定自然数1, … , n的一个排列，例如，(2, 1, 5, 3, 4)，如果 j > i 但j 排在i 的前面则称(j,

i)为该排列的一个逆序。在上例中 (2, 1)，(5, 3) , (5,4)为该排列的逆序。该排列总共有3 个逆序。

1) 试用分治法设计一个计算给定排列的逆序总数的算法. (8分) 2) 分析算法的时间复杂度。（7分） 解：算法的伪代码如下：

1） 将输入排列A[1,n]在中间分成两个子排列A[1,n/2]和A[n/2+1,n]； 2） 递归对这两个子排列应用该算法，得到逆序数为n1和n2； 3） 对这两个子排列排序；

4） 使用线性时间算法计算排序后两个子排列间的逆序数，设其为n3； 5） n1+n2+n3即为原始的输入排列的逆序数；

计算排序后两个子排列间的逆序数的算法可在合并（merge）算法的基础上得到。 上述算法的时间复杂度为：

n1dt(n)2t(n/2)cnlogn

n1

按Master定理，t(n)= Θ(nlog2n)

4. 考虑0≤xi ≤1而不是xi Є{ 0 , 1 }的连续背包问题。一种可行的贪婪策略是：按

价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其装入；否则，往背包中装入此物品的一部分。

1) 对于n=3, w=[100,10,10], p= [ 2 0 , 1 5 , 1 5 ]及c= 1 0 5 ,上述装入方法获得的结果是什么？ (7分)

2) 证明这种贪婪算法总能获得最优解。（8分）

解： （1）首先计算三种物品的价值密度向量[0.2,1.5,1.5]，并重新排序得：

W’=[10,10,100], p’= [ 15 , 1 5 , 20 ]；

然后按要求的贪婪策略装入重新排序的物品1，2，此时装入背包中的物品总价值为30，占用容量为20，剩余容量为85；

最后，装入剩余物品的一部分即0.85倍，价值为0.85*20=17；

所以，总价值为30+17=47，装包方法为(1,1,0.85),回复到原顺序为（0.85,1,1）。

（2） 假设物品已按价值密度非递减的顺序排列，x1 ... xn是贪心法得到的解，y1 ... yn是最优解。下面我们可以证得这两组解得到的价值总值是相等的，从而贪心法得到的解是最优的。 假设j是使得(xi=yi, 1≤i yj。通过减小yj+1、yj+2、…，增加yj的方法，可以增加yj到xj，因为是用高价值密度的物品代替低价值密度或等价值密度的物品，所以背包总价值不可能降低。通过这种转换，得到一个新的最优解y1 ... yn，新的最优解与贪心法得到的解相比，如果存在j1使得(xi=yi, 1≤i重复做这样的转换，可以将最初的最优解转化为贪心解，并且不会降低背包的价值，因此这种贪心算法总能获得最优解。

5. /1/2 Knapsack problem：具有权重(w1,w2,...wn)及效益值(p1,p2,...pn)的n个物品，

放入到容量为c的背包中，使得放入背包中的物品效益值最大，即max(并满足下面约束条件：

ni1ix*pi)

ni1ix*wic，and xi{0,1,2}1in。

（1） 证明0/1/2背包问题满足最优子结构性质 （7分）。 （2） 定义最优值函数（3）

（3） 给出用动态规划算法求解最优值的递归方程 （5）。

解： （1）权重(w1,w2,...wn)及效益值(p1,p2,...pn)的n个物品，放入到容量为c的背包中。假设(x1,x2,...xn)（xi(0,1,2)）是该问题的最优解，

不失一般性，对于子问题(w1,w2,...wn1)及(p1,p2,...pn1)的n-1个物品，及容量

cxnwn，则(x1,x2,...xn1)（xi(0,1,2)）是该子问题的最优解。因为：

1）

x*wcxw 即(x,x,...x)为子问题的可行解，由于： x*wx*wxwc x*wcxwi1iinnn112n1nn1i1in1i1ii1iinniinn2）(x1,x2,...xn1)也是该子问题的最优解。否则，假设(y1,y2,...yn1)是该子问题的最优解，那么：

n1i1n1i1n1i1yi*pii1xi*pi，因而

yi*pixnpni1xi*pixnpn，同时，

yi*wixnwnc即(y1,y2,...yn1,xn)是原问题的可行解，这与

n1n1(x1,x2,...xn)是原问题的最优解相矛盾。

所以，0/1/2背包问题满足最优子结构性质，即最优解包含的子问题的解也是最优的

(2) 定义f(i,y)为物品从i到n，背包容量为y时最优装箱方案对应的效益值 (3) 最优值的递归方程:

0ifwnyf(n,y)pnifwny2wn

2*pify2wnn

f(i1,y)ifwiyf(i,y)max{f(i1,y),f(i1,ywi)pi}ifwiy2wi

max{f(i1,y),f(i1,yw)p,f(i1,y2w)2p}ify2wiiiin

6. 装配线调度问题: 如下图所示，有2个装配线，每一个装配线上有n个装配站，

site[i,j]表示i个装配线上的j个装配站。两个装配线上相同位置的转配站有相同的功能。 在装配站site[i,j]上花费时间为Cost[i,j]。进入和退出装配线i,j的时间分别为in[i,j]和out[i,j]. 从一个装配站到相同装配线的下一个的时间忽略不计，到不同的装配站的时间为transfer[i][j]。利用动态规划算法给出时间最少的装配方案。要求： （1） 定义最优值函数（3） （2） 给出最优值的递归方程 （6） （3） 写出实现递归方程的伪代码 （6）

In(1,i)1,11,21,i-1Cost(1,4)1,iout(1,i)1 n-11nanTr1s((,i)2,12,22,i-1In(2,i)Trans(2,i)S……e2.iCost(2,4)out(2,i)2 n-12n

解： （1） 定义f(i,j)为从初始状态到第i条装配线第j个装配站的所用的最少时间，则初始状态：f(1,1)in(1,1)cost(1,1)，

f(1,1)in(2,1)cost(2,1)最终完成时间fmin{f(1,n)out(1,n),f(2,n)out(2,n)}。 下面的结果也同样得满分：

由于从一个装配站到相同装配线的下一个的时间忽略不计，因此只需考虑从初始状态进入装配线的时间及退出装配线的时间，故对所有in[i,j]中j只能为1，对于所有out[i,j]，j只能为n，所以上式也可以记为：

f(1,1)in(1)cost(1,1) fmin{f(1,n)out(1),f(2,n)out(2)} f(1,1)in(2)cost(2,1)（2）递归关系：

f(1,j)min{f(1,j1)cost(1,j),f(2,j1)trans(2,j)cost(1,j)}f(2,j)min{f(2,j1)cost(2,j),f(1,j1)trans(1,j)cost(2,j)}

（3）伪代码

f(1,1)in(1)cost(1,1) f(2,1)in(2)cost(2,1)

for j=2 to n do

f(1,j)min{f(1,j1)cost(1,j),f(2,j1)trans(2,j)cost(1,j)} f(2,j)min{f(2,j1)cost(2,j),f(1,j1)trans(1,j)cost(2,j)} End for

Return min{f(1,n)out(1),f(2,n)out(2)}

7. 子集和数问题: 已知n+1个正数：wi, 1in, 和M。要求找出{wi }的所有子集使得子集

内元素之和等于M，用n元组的方法表示解向量，要求： （1） 给出回溯方法求解该问题的两种限界方法（6） （2） 给出利用上述限界条件的回溯法伪代码（9）。

解：用定长元组的方法表示解向量，即(x1,x2,...xn)（xi{0,1})

（1） 两种限界条件分别为： a)

W(i)X(i)W(i)M

i1ik1knb) 将wi按非递减排序

W(i)X(i)W(k1)M

i1k（2）伪代码表示如下：

1) Let s=w(1)x(1)+…+w(k-1)x(k-1)

r=w(k)+…+w(n), assume s+r≥M

2) Expanding left child node

a) If S+W(k)+W(k+1)>M then i.

stop expanding

ii. iii. b) Else i. ii. iii.

r←r-w(k),

Expanding right child node; X(k)←1 , s←s+w(k)，

r←r-w(k)，let (x(1),…,x(k)) be E-Node;

3) Expanding right child node ：

a) If s+rM then stop expanding ; i.

Else ,X(k)←0