用動(dòng)態(tài)規(guī)劃的思想實(shí)現(xiàn)動(dòng)態(tài)投資問題實(shí)驗(yàn)報(bào)告

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

1、算法實(shí)驗(yàn)報(bào)告二??動(dòng)態(tài)規(guī)劃法????????????????????????一、實(shí)驗(yàn)?zāi)康模河脛?dòng)態(tài)規(guī)劃的思想實(shí)現(xiàn)動(dòng)態(tài)投資問題。二、實(shí)驗(yàn)要求：掌握動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)的基本策略。三、實(shí)驗(yàn)內(nèi)容：m元錢，n項(xiàng)投資，fi(x)將x元投入第i項(xiàng)項(xiàng)目的效益，?目標(biāo)函數(shù)max{f1(x1)+f2(x2)+…+?fn(xn)}?約束條件x1+x2+…+xn=m，xi∈N設(shè)Fk(x)表示x元錢投給前k個(gè)項(xiàng)目的最大效益算法實(shí)現(xiàn)：投資第k個(gè)項(xiàng)目p元錢的效益可表示為Project[k][p],其中0<=k<=n,0<=p<=m;設(shè)投資

2、給前k個(gè)項(xiàng)目p元?錢的最終總效益為用Benefit[k][p],其中0<=k<=n,0<=p<=m。設(shè)allot[k][p]表示在總投資為p元錢時(shí)候，最終分配給第k個(gè)項(xiàng)目的錢數(shù)解。四、實(shí)驗(yàn)心得：在調(diào)試過程中出現(xiàn)了好多小問題，一開始結(jié)果不對(duì)，我通過單步調(diào)試一步步的看待填的二維表中的數(shù)據(jù)。發(fā)現(xiàn)大部分V[i][j]對(duì)了，但是有極小數(shù)的不對(duì)。故而我的結(jié)果出現(xiàn)了問題。通過本次實(shí)驗(yàn)加深了我對(duì)動(dòng)態(tài)規(guī)劃算法的理解。而且對(duì)動(dòng)態(tài)規(guī)范編寫代碼解決一個(gè)實(shí)際問題有了進(jìn)一步的認(rèn)識(shí)。即當(dāng)算法考慮的原問題的每一個(gè)子問題，算法都需要計(jì)算一

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