用動態(tài)規(guī)劃的思想實現(xiàn)動態(tài)投資問題實驗報告

《用動態(tài)規(guī)劃的思想實現(xiàn)動態(tài)投資問題實驗報告》由會員上傳分享，免費在線閱讀，更多相關內容在應用文檔-天天文庫。

1、算法實驗報告二??動態(tài)規(guī)劃法????????????????????????一、實驗目的：用動態(tài)規(guī)劃的思想實現(xiàn)動態(tài)投資問題。二、實驗要求：掌握動態(tài)規(guī)劃算法設計的基本策略。三、實驗內容：m元錢，n項投資，fi(x)將x元投入第i項項目的效益，?目標函數(shù)max{f1(x1)+f2(x2)+…+?fn(xn)}?約束條件x1+x2+…+xn=m，xi∈N設Fk(x)表示x元錢投給前k個項目的最大效益算法實現(xiàn)：投資第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個項目的錢數(shù)解。四、實驗心得：在調試過程中出現(xiàn)了好多小問題，一開始結果不對，我通過單步調試一步步的看待填的二維表中的數(shù)據(jù)。發(fā)現(xiàn)大部分V[i][j]對了，但是有極小數(shù)的不對。故而我的結果出現(xiàn)了問題。通過本次實驗加深了我對動態(tài)規(guī)劃算法的理解。而且對動態(tài)規(guī)范編寫代碼解決一個實際問題有了進一步的認識。即當算法考慮的原問題的每一個子問題，算法都需要計算一

3、個最優(yōu)解。換句話說，所有算法生成的表項表示算法考慮的子問題的最優(yōu)解。這時候用動態(tài)規(guī)范把每一個最優(yōu)解求出來（利用遞歸公式），就能夠保證最后求得的一定是最優(yōu)解。而且動態(tài)規(guī)劃有個特點，即它是由底向上，它實現(xiàn)起來就是利用循環(huán)，有時用到一層循環(huán)即可，有時要用到兩層for循環(huán)即可以求解出問題。五：附錄：程序代碼及結果#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("");}