算法分析与设计实验报告--动态规划.doc

《算法分析与设计实验报告--动态规划.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法分析与设计》实验报告完成日期：20011.11.241、实验目的(1)掌握动态规划方法贪心算法思想(2)掌握最优子结构原理(3)了解动态规划一般问题2、实验内容(1)编写一个简单的程序，解决0-1背包问题。设N=5，C=10，w={2，2，6，5，4},v={6,3,5,4,6}(2)合唱队形安排。【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK

2、，则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。3、实验要求（1）写出源程序，并编译运行（2）详细记录程序调试及运行结果4、算法思想：利用动态规划的思想，解决诸如0—1背包问题，最大合唱队形问题等问题的最优解，能在最短的时间内，找到最好的解决方案的一种算法。5、实验过程：1、0—1背包问题：源代码如下：#include#includeusingnamespaces

3、td;#defineN5#definec10intw[N+1]={0,2,2,6,5,4},v[N+1]={0,6,3,5,4,6};intm[N+1][c+1];intmin(intx,inty){if(x<=y)returnx;elsereturny;}intmax(intx,inty){if(x>=y)returnx;elsereturny;}voidKnapSack(intv[],intw[]){intjMax=min(w[1],c);for(intj=1;j<=jMax;j++)//当0=

4、n]时,m(n,j)=0m[1][j]=0;for(j=w[1];j<=c;j++)//当j>=w[n]时,m(n,j)=v[n]m[1][j]=v[1];for(inti=2;i<=N;i++)//DP{intjMax=min(w[i],c);for(j=1;j=w[n]m[i][j]=max(m[i-1][j],m[i-1][

5、j-w[i]]+v[i]);}}voidmain(){KnapSack(v,w);for(inti=1;i<=N;i++){for(intj=0;j<=c;j++)cout<#includeusingnamespacestd;#defineMAXN200voidmain(){intn,a[MAXN],b[MAXN],c[MAXN],i,j,max,lab,p

6、re[MAXN];cout<<"输入数据个数：";cin>>n;cout<<"输入"<>a[i];memset(b,0,sizeof(a));memset(c,0,sizeof(c));b[1]=1;pre[i]=0;//i=1->nfor(i=2;i<=n;i++){max=0;for(j=i-1;j>=1;j--){if(a[j]max){max=b[j];pre[i]=j;}}b[i]=max+1;}

7、//lab:max所对应a数组元素下标O(n)max=b[1];for(i=2;i<=n;i++){if(b[i]>max){max=b[i];lab=i;}}cout<<"LongestIncreasingSubsequenceis："<0){c[j--]=a[i];i=pre[i];num--;}//输出数列O(n)for(i=1;i<=max;i++)cout<

8、t<