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

用动态规划的思想实现动态投资问题 实验报告（共1篇）

用动态规划的思想实现动态投资问题 实验报告 篇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;设投资给前k个项目p元 钱的最终总效益为用Benefit[k][p]，其中0<=k<=n,0<=p<=m。设allot[k][p]表示在总投资为p元钱时候，最终分配给第k个项目的钱数解。

四、实验心得：在调试过程中出现了好多小问题，一开始结果不对，我通过单步调试一步步的看待填的二维表中的数据。发现大部分V[i][j]对了，但是有极小数的不对。故而我的结果出现了问题。通过本次实验加深了我对动态规划算法的理解。而且对动态规范编写代码解决一个实际问题有了进一步的认识。即当算法考虑的原问题的每一个子问题，算法都需要计算一个最优解。换句话说，所有算法生成的表项表示算法考虑的子问题的最优解。这时候用动态规范把每一个最优解求出来（利用递归公式），就能够保证最后求得的一定是最优解。而且动态规划有个特点，即它是由底向上，它实现起来就是利用循环，有时用到一层循环即可，有时要用到两层for循环即可以求解出问题。

五：附录：程序代码及结果

#include

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(“可获得的最大收益为：%dn”,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(s>f[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;i>0;i--){

s = s-k[i+1];

k[i] = d[i][s];} for(i=1;i<=3;i++)

} printf(“%5d”,k[i]);printf(“n”);