算法的一些习题,一 完成下列关于复杂度的问题（1）使用定义证明：证明2n=o(n2) （2）使用master定理求解T(

算法的一些习题,
一 完成下列关于复杂度的问题
（1）使用定义证明：证明2n=o(n2)
（2）使用master定理求解T(n) = 9T(n/3) +n
二 请举例说明分治算法、动态规划算法、贪心选择算法、回溯算法和分支限界算法在
实际应用中的特点和求解的适用条件.
三 c[i][j]的递归关系的含义：
c[i][j]为序列“a0,a1,…,ai-2”和“b0,b1,…,bj-1”的最长公共子序列的长度,
计算c[i][j]可递归地表述如下：
（1）c[i][j]=0\x05\x05\x05\x05\x05\x05\x05如果i=0或j=0；
（2）c[i][j]= c[i-1][j-1]+1\x05\x05\x05\x05如果i,j>0,且a[i-1]=b[j-1]；
（3）c[i][j]=max（c[i][j-1],c[i-1][j]）\x05如果i,j>0,且a[i-1]!=b[j-1].
请详细解释每一个递归关系的来源以及理论根据.
四 0/1背包算法,给出自底向上实现五个物品重量w=(3,4,7,8,9) ,物品价值v=(4,5,10,11,13) 背包容量c=17时使用动态规划算法求解的矩阵.绘制出5*17的表格,并填充,说明每一行数据的来源.
五 当使用两角、1角、5分、1分的硬币来找零时.设计一个找n分钱的贪心算法.
并分析时间复杂度和空间复杂度.
六．工作分配问题.设有n件工作要分配给n个人去完成.将工作i分配给第j个人
所需的费用为Cij.设计一个算法找出最优解,为每一个人都分配1件不同的工作,
并使总费用达到最小,并说明算法的正确性.（给出分析过程并写出实现程序）.
七．根据分支限界法的01背包,
（1）分支限界法01背包问题中bound的作用以及实现的策略
（2）为什么右儿子结点一定是可行结点
（3）如何构造最优解的,请详细描述实现的策略.
下面是一段核心代码：
while (i = n+1) {// 非叶结点
Typew wt = cw + w[i];
if (wt bestp) bestp = cp+p[i];
AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}
up = Bound(i+1);
if (up >= bestp)
AddLiveNode(up,cp,cw,false,i+1);

如果k不等于i,则交换a[i]和a[k]的值
Temp=a[i]; /把a[i]的值放到一个临时变量里
A[i]=a[k]; //a[k]的值给a[i]
A[k]=temp; //temp的值,也就是原来的a[i]给a[k]
K=i; //原来k等于i
For(j=i+1;j<8;j++)
If(a[k]>a[j])k=j;//在比较之后如果有小于a[k]=a[i]的a[j]那么k=j了,就不等于i了