实验三 动态规划算法

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

1、实验三动态规划算法一、实验目的进一步理解动态规划算法的基本思想，掌握设计有效算法的动态规划方法，会使用动态规划解决一些实际问题。二、实验要求1、上机前的准备工作根据实验内容中所给题目，利用所学动态规划算法的基本设计思想设计算法并编写好上机程序，以提高上机效率；2、独立上机，输入、调试所编程序；3、上机结束后，写出实验报告。4、上机时间：4学时三、实验内容算法实现题：1、3-3#includeusingnamespacestd;constintN=4;ints[2*N]={0,3,4,2,1,3,4,2};//一共4堆石子，3,4,2,1intm[2*N][

2、2*N];inth[2*N][2*N];inttotalValue(inti,intj){intsum=0;for(intk=i;k<=j;k++)sum+=s[k];returnsum;}voidmaxsum(intn)//求最大值{inti,j,r,k,t;for(i=1;i<=n;i++)m[i][i]=0;for(r=2;r<=n;r++)for(i=1;im[i][j]){m[i][j

3、]=t;h[i][j]=k;}}m[i][j]+=totalValue(i,j);}}voidminsum(intn)//求最小值{inti,j,r,k,t;for(i=1;i<=n;i++)m[i][i]=0;for(r=2;r<=n;r++)for(i=1;i

4、back(inti,intj,inth[][2*N]){if(i==j)return;Traceback(i,h[i][j],h);Traceback(h[i][j]+1,j,h);cout<m[i][n-1+i]){p=i;q=n-1+i;min_result=m[p][q];}cout<<"最小值："<

5、ceback(p,q,h);maxsum(2*n);intmax_result=m[1][n];p=1;q=n;for(i=2;i<=n;i++)if(max_result

6、<<"pleaseinputthenumberofrows:";//输入行数cin>>n;for(i=1;i<=n;i++)for(j=1;j<=i;j++){cin>>data[i][j];//将数据放到二维数组a[i][j]=data[i][j];b[i][j]=0;}for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)if(a[i+1][j]>a[i+1][j+1]){a[i][j]=a[i][j]+a[i+1][j];b[i][j]=0;}else{a[i][j]=a[i][j]+a[i+1][j+1];b[i][j]=1;}cout<<"max=

7、"<";j=j+b[i][j];}cout<usingnamespacestd;constintN=4;intm[N+1][N+1]={{0,0,0,0,0},{0,0,5,8,20},{0,0,0,7,18},{0,0,0,0,2},{0,0,0,0,0}};inth[N+1][N+1];//由矩阵连乘