资源描述：
《《算法分析与设计》作业答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《算法分析与设计》作业1、考虑而不是xi∈{0，1}的连续背包问题。一种可行的贪婪策略是：按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其装入；否则，往背包内装如此物品的一部分。(a)对于n=3，w=[100,10,10]，p=[20,15,15]，以及c=105，上述装入法获得结果是什么？(b)证明这种贪婪算法总能获得最优解。(c)用伪代码描述此算法。答：（a）利用贪婪算法，按价值密度考察的背包为w2，w3，w1；背包w2和w3重20，还可以容纳85，由于，背包w1还可以装入x1=0.85
2、，则背包内物品总价值为15+15+20*0.85＝47.（b）假设已按价值密度排好序，考察w1,w2,……,wi，……，对应的价值为p1,p2,……,pi,……如果装到pi-1再装pi时，恰好要取xi个wi。（）因为比它价值密度大的都已装载完，所以此时获得的为最优解。（c）算法描述如下：templateintContainerLoading(intx[],Tw[],Tc,intn){int*t=newint[n+1];IndirectSort(w,t,n);for(inti=1;i<=n;i++
3、)x[i]=0;for(i=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c+=w[t[i]];}delete[]t;}152、证明当且仅当二分图没有覆盖时，下述算法找不到覆盖。m＝0;//当前覆盖的大小对于A中的所有i，New[i]=Degree[i]对于B中的所有i，Cov[i]=falsewhile(对于A中的某些i，New[i]>0){设v是具有最大的New[i]的顶点；C[m++]=v;for(所有邻接于v的顶点j){If(!Cov[j]){Cov[j]=true;对于所有邻接于
4、j的顶点，使其New[k]减1}}}if(有些顶点未被覆盖)失败else找到一个覆盖2）给出一个具有覆盖的二分图，使得上述算法找不到最小覆盖。证明：如果二分图有覆盖，则通过以上贪婪算法，总能得到最小覆盖A’。首先假定A’为空集当更多的顶点可被覆盖时，把能覆盖未被覆盖的顶点数目最多的顶点加入A’如果有些顶点未被覆盖，则失败，否则总能找到一个覆盖。所以只有当二分图没有覆盖时，才会失败而找不到覆盖，否则总能找到一个覆盖A’。2）令S={S1，...，S5},U={4，5，...，15},S1={4，6，7，8，9，1
5、3}，S2={4，5，6，8}，S3={8，10，12，14，15}，S4={5，6，8，12，14，15}，S5={4，9，10，11}。通过以上算法，得S'={S1，S2，S4，S5}实际最小覆盖为{S1，S4，S5}3、15对于二分图覆盖问题设计另一种贪婪启发算法，贪婪准则是：如果B中某一个顶点被A中一个顶点覆盖，选择A中这个顶点；否则，从A中选择一个顶点，使得它所覆盖的未被覆盖的顶点数目最多。给出这种贪婪算法的伪代码。解答：贪婪算法的伪代码为:m=0//当前覆盖的大小对于A中的所有i,Out[i]=ou
6、tdegree[i];对于B中的所有i,In[i]=indegree[i];对于B中的所有i,Cov[i]=false;for(对于B中所有入度为1的顶点i){设v是邻接于B[i]的顶点C[m++]=v;for(所有邻接于v的顶点j){if(!Cov[j]){Cov[j]=true;对于所有邻接于j的顶点，使其Out[k]减1}}}while(对于A中的某些i,Out[i]>0){设v是具有最大Out[i]的顶点C[m++]=v;for(所有邻接于v的顶点j){if(!Cov[j]){Cov[j]=true;对
7、于所有邻接于j的顶点，使其Out[k]减1}}}if(有些顶点未被覆盖)失败else找到一个覆盖4、有n个硬币，其中1个是假币，且假币较轻。请用分而治之方法设计一个找出假币的算法。151）用伪代码描述你的算法；2）用C程序描述你的算法；3）分析你的算法的时间复杂性。解答：代码如下Feit_money(low,high)//假定伪币较真币轻{floatmid;ifhigh-low=1thenifA[low]A[high]returnA[h
8、igh];elsemid=(low+high)/2;if(high-low+1)%2==0thensum1=sum(low,mid);sum2=sum(mid+1,high);elsesum1=sum(low,mid-1);sum2=sum(mid+1,high);endififsum1=sum2thenreturnA[mid];elseifsum1
