為了方便廣大考生更好的復(fù)習(xí)，小編編輯整理提供了2011年C語言輔導(dǎo)實(shí)例編程(八)，以供各位考生復(fù)習(xí)參考，希望對考生復(fù)習(xí)有所幫助。

最大化投資回報問題的實(shí)現(xiàn)

最大化投資回報問題：某人有一定的資金用來購買不同面額的債卷，不同面額債卷的年收益是不同的，求給定資金，年限以及債卷面額、收益的情況下怎樣購買才能使此人獲得最大投資回報。

程序輸入約定：第一行第一列表示資金（1000的倍數(shù)）總量，第二列表示投資年限;第二行表示債卷面額總數(shù);從第三行開始每行表示一種債卷，占用兩列，前一列表示債卷面額，后一列表示其年收益，如下輸入實(shí)例，

100001

2

4000400

3000250

程序?qū)崿F(xiàn)如下，注釋幾乎說明了一切，所以不再另外分析。

///此數(shù)組是算法的關(guān)鍵存儲結(jié)構(gòu)，用來存儲不同階段各種債卷

///組合下對應(yīng)可獲取的最大利息。

intsaifa［80005］;

///此函數(shù)用于計算當(dāng)前債卷在不同購買額下的最優(yōu)利息情況，

///注意此時的利息情況是基于上一次債卷的情況下計算得到的，

///也就是說當(dāng)前利息最優(yōu)是基于上一次利息最優(yōu)的基礎(chǔ)上計算出來的，

///這也正好體現(xiàn)了動態(tài)規(guī)劃中“最優(yōu)化原則”：不管前面的策略如何，

///此后的決策必須是基于當(dāng)前狀態(tài)（由上一次決策產(chǎn)生）的最優(yōu)決策。

/*

動態(tài)規(guī)劃的求解過程一般都可以用一個最優(yōu)決策表來描述，

對于本程序，以示例輸入為例，對于第一年，其最優(yōu)決策表如下：

在以前購買了0張4000的債卷的基礎(chǔ)上再2張3000的，也可以在以前購

買了1張4000的基礎(chǔ)上再買1張3000，經(jīng)比較取其收益大的，這就是典

型的動態(tài)規(guī)劃中的當(dāng)前最優(yōu)狀態(tài)計算。

本程序中把上面的最優(yōu)決策二維表用一個一維數(shù)組表示，值得借鑒。

*/

voidadd（inta，intb）

{cout《《a《《“”《《b《《endl;//fordebug

for（inti=0;i《=80000;i++）

{

if（i+a》80000）

{

break;

}

if（saifa［i］+b》saifa［i+a］）//累計同時購買多種債卷時的利息

{

saifa［i+a］=saifa［i］+b;

}

if（i《200）//fordebug

cout《《i《《“-”《《saifa［i］《《“”;

}

cout《《endl;//fordebug

}

intmain（void）

012345678910（*1000）--（1）

0000400400400400800800800--（2）

000250400400500650800900900--（3）

（1）--表示首先選利息為400的債卷在對應(yīng)資金下的最優(yōu)利息。

（2）--表示可用來購買債卷的資金。

（3）--表示在已有狀態(tài)下再選擇利息為300的債卷在對應(yīng)資金下的最優(yōu)利息。

注意上面表格，在求購買利息為300的債卷獲得的最優(yōu)收益的時候，

參考了以前的最優(yōu)狀態(tài)，以3行8列的650為例，7（*1000）可以

{

intn，d，money，year，pay，bond;

intii，i;

for（ii=0;ii

{

memset（saifa，0，sizeof（saifa））;

scanf（“%d%d”，&money，&year）;

scanf（“%d”，&d）;

for（i=0;i

{

scanf（“%d%d”，&pay，&bond）;

add（pay/1000，bond）;

}

//計算指定年限內(nèi)最優(yōu)組合的本金利息總額

for（i=0;i

{cout《《saifa［money/1000］《《“”;//fordebug

money+=saifa［money/1000］;

}

cout《《endl;//fordebug

printf（“%d\n”，money）;

}

return0;

}

上述程序?qū)崿F(xiàn)方法同樣適合于背包問題，最優(yōu)庫存問題等，只是針對具體情況，最優(yōu)決策表的表示和生成會有所不同。