問題17投資

?

合理分配資源，投入到某些事項(xiàng)上，希望得到最好的綜合匯報(bào)，這類追求很有意義，得到了廣泛的研究。當(dāng)然，如果在現(xiàn)實(shí)中，這種事情的復(fù)雜度是很高的。

?

如果把問題簡(jiǎn)化，就變成了一個(gè)在動(dòng)態(tài)規(guī)劃（一種經(jīng)典的算法設(shè)計(jì)方法）學(xué)習(xí)中的經(jīng)典例題。

?

本章從一個(gè)簡(jiǎn)單的投資例子引入問題

給定總投資亮n（整數(shù)），和m個(gè)單增項(xiàng)目回報(bào)函數(shù)fk(x): 將x投入到第k個(gè)項(xiàng)目中的效益。

把n分成m份，滿足，m份的和為n，且m個(gè)回報(bào)函數(shù)值的和最大。

?

求解這個(gè)問題，要用到動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)方法。

?

本章給出了詳細(xì)求解思路，算法描述、算例分析和算法性質(zhì)描述。

?

【作者感受】

本章從一個(gè)很有吸引力的問題入手，其實(shí)是介紹動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃是算法設(shè)計(jì)的必學(xué)方法，有點(diǎn)難。但是如果一個(gè)問題能設(shè)計(jì)出動(dòng)態(tài)規(guī)劃算法，而且能實(shí)現(xiàn)，其執(zhí)行效率是很高的。

真的投資比這個(gè)復(fù)雜的多的多。