用动态规划的思想实现动态投资问题实验报告

《用动态规划的思想实现动态投资问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法实验报告二  动态规划法                        一、实验目的：用动态规划的思想实现动态投资问题。二、实验要求：掌握动态规划算法设计的基本策略。三、实验内容：m元钱，n项投资，fi(x)将x元投入第i项项目的效益， 目标函数max{f1(x1)+f2(x2)+…+ fn(xn)} 约束条件x1+x2+…+xn=m，xi∈N设Fk(x)表示x元钱投给前k个项目的最大效益算法实现：投资第k个项目p元钱的效益可表示为Project[k][p],其中0<=k<=n,0<=p<=m;设投资

2、给前k个项目p元 钱的最终总效益为用Benefit[k][p],其中0<=k<=n,0<=p<=m。设allot[k][p]表示在总投资为p元钱时候，最终分配给第k个项目的钱数解。四、实验心得：在调试过程中出现了好多小问题，一开始结果不对，我通过单步调试一步步的看待填的二维表中的数据。发现大部分V[i][j]对了，但是有极小数的不对。故而我的结果出现了问题。通过本次实验加深了我对动态规划算法的理解。而且对动态规范编写代码解决一个实际问题有了进一步的认识。即当算法考虑的原问题的每一个子问题，算法都需要计算一

3、个最优解。换句话说，所有算法生成的表项表示算法考虑的子问题的最优解。这时候用动态规范把每一个最优解求出来（利用递归公式），就能够保证最后求得的一定是最优解。而且动态规划有个特点，即它是由底向上，它实现起来就是利用循环，有时用到一层循环即可，有时要用到两层for循环即可以求解出问题。五：附录：程序代码及结果#includevoidmain(){voidjie(int,int,intd[][9]);voidInvest(intm,intn,intf[][9],intg[][9],intd[]

4、[9]);intm=8,n=3,f[4][9],d[4][9];intg[4][9]={{0},{0,5,15,40,80,90,95,98,100},{0,5,15,40,60,70,73,74,75},{0,4,26,40,45,50,51,53,53}};Invest(m,n,f,g,d);printf("可获得的最大收益为：%d",f[3][8]);jie(m,n,d);}voidInvest(intm,intn,intf[][9],intg[][9],intd[][9]){inti,j,k,

5、s;for(j=0;j<=m;j++){f[1][j]=g[1][j];d[1][j]=j;}for(i=2;i<=n;i++)for(j=0;j<=m;j++){f[i][j]=0;for(k=0;k<=j;k++){s=f[i-1][j-k]+g[i][k];if(s>f[i][j]){f[i][j]=s;d[i][j]=k;}}}}voidjie(intm,intn,intd[][9]){ints=m;intk[4];inti;k[n]=d[n][m];for(i=n-1;i>0;i--){s=s-

6、k[i+1];k[i]=d[i][s];}for(i=1;i<=3;i++)printf("%5d",k[i]);printf("");}