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

算法实验报告二?? 动态规划法 ??????????????????????? ?一、实验目的要求：、m元钱，n项投资， 将x元投入第项项目的效益，? 目标函数max {f1(x1) + f2(x2) + … +? }? 约束条件x1 + x2 + … + xn = m，xi N 设Fk(x) 表示x元钱投给前k个项目的最大效益算法实现投资第k个项目p元钱的效益可表示为Project[k][p],其中0=k=n,0=p=m;设投资给前k个项目p元?钱的最终总效益为用Benefit[k][p],其中0=k=n,0=p=m。设allot[k][p]表示在总投资为p元钱时候，最终分配给第k个项目的钱数解。 、在调试过程中出现了好多小问题，一开始结果不对，我通过单步调试一步步的看待填的二维表中的数据。发现大部分V[i][j]对了，但是有极小数的不对。故而我的结果出现了问题。通过本次实验加深了我对算法的理解。而且对动态规范编写代码解决一个实际问题有了进一步的认识。即当算法考虑的原问题的每一个子问题，算法都需要计算一个最优解。换句话说，所有算法生成的表项表示算法考虑的子问题的最优解。这时候用动态规范把每一个最优解求出来（利用递归公式），就能够保证最后求得的一定是最优解。而且动态规划有个特点，即它是由底向上，它实现起来就是利用循环，有时用到一层循环即可，有时要用到两层for循环即可以求解出问题。 #includestdio.h void main() { void jie(int,int,int d[][9]); void Invest(int m,int n,int f[][9],int g[][9],int d[][9]); int m=8,n=3,f[4][9],d[4][9]; int g[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\n,f[3][8]); jie(m,n,d); } void Invest(int m,int n,int f[][9],int g[][9],int d[][9]) { int i,j,k,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(sf[i][j]) { f[i][j]=s; d[i][j]=k; } } } } void jie(int m,int n,int d[][9]){ int s=m; int k[4]; int i; k[n]=d[n][m]; for(i=n-1;i0;i--) { s = s-k[i+1]; k[i] = d[i][s]; } for(i=1;i=3;i++) printf(%5d,k[i]); printf(\n); }