c语言背包问题_背包问题贪心算法_背包问题 贪心算法(5)

（每个分枝1分，或者是每层2分，共6分）

（2）当耗费大于等于当前最优值时，剪枝。（1分）

（3）见上图。（每2个╳ 1分，共2分）

（4）最优值： 9 （1分）

最优解：2，1，3

４．（８分）给定两个序列X=<A,B,C,B,A>，Y=<B,D,C,A,B>，请采用动态规划策略求出其最长公共子序列。要求给出过程。

答：

j 0 1 2 3 4 5

i yi B D C A B

0 xi 0 0 0 0 0 0

1 A 0 0 0 0 1 1

2 B 0 1 1 1 1 2

3 C0 1 1 2 2 2

4 B 0 1 1 2 2 3

5 Ａ 0 1 2 2 2 3

（上述表内每一行一分，共６分）

最长公共子序列为<B，C，B>（２分）

5．（2分）考虑n=3时的0-1背包问题的实例：W={15,10,10}，P={50,30,30}，c=20。当x[1]=1，x[2]=0时，请计算Bound(2)。

答：

Bound(3)=50+5/10 * 20 = 65 (2分)

三、算法填空题（共10分，每空2分）

给定n种物品和一个背包，物品i的重量是w[i], 其价值是p[i], 背包的容量为c。设物品已按单位重量价值递减的次序排序。每种物品不可以装入背包多次，但可以装入部分的物品i。求解背包问题的贪心算法如下：

float Knapsack (float x[ ], float w[ ], float p[ ],float c, int n)

{ float maxsum= ; // maxsum表示装进包的物品价值总和

for ( int i=1;i<=n; i++) x[i]=0 // x[i]=0表示第i个物品未装进包

for ( )

if( )

{ x[i] =1;

maxsum+= ;

c- = w[i];

}

else break;

if (c>0) {x[i]=c/w[i]; ;}

return maxsum;

}

答：(共５个空，每空2分，总计10分)

０

int i=1；i<=n；ｉ++

w[i]<=C

p[i]

maxsum+ = p[i] * c / w[i]

四、算法设计及分析题（共45分）

1．（20分）请用分治策略设计递归的二分检索算法，并分析其时间复杂性（要求给出每个阶段所花的时间，在此基础上列出递归方程，并求出其解的渐进阶）。

答：（此题解法不唯一）

算法：

int bsearch(A[],K,L,H) （1分）

{ if (H<L) return(-1); (2分)

else

{ mid=(L+H) /2; (2分)

if (A[mid] == K) (1分)

return(mid)； (1分)

else if （A[mid]>K） (2分)

return(bsearch(A,K,L, mid-1)) ; (2分)

else return(bsearch(K, mid+1,H)); (2分)

}

}

算法时间复杂性分析：

∵ Divide阶段所花时间为O(1) (1分)

Conquer阶段所花时间为T(n/2) (1分)

merge阶段没有花时间（或者说，merge阶段所花时间为O(1)） (1分)

∴算法时间复杂性递归方程如下：

T(n)=O(1) 当n≤0

T(n)= T(n/2)+O（1） 当n>1 (2分)

用套用公式法（master method）求解递归方程：

∵a=1,b=2,

f(n)=O(1), ∴与f(n)同阶

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-23877-5.html