李曉明

人們常常講，要合理分配時(shí)間，合理分配資金等。抽象來看，說的都是要將某種掌握的資源，分配投入到某些事項(xiàng)上，希望得到最好的綜合回報(bào)。這類追求很有意義，因而得到人們的廣泛研究。同時(shí)這種事情也很復(fù)雜，到目前為止并沒有一個(gè)普適的方案。其復(fù)雜性體現(xiàn)在幾個(gè)方面：第一，每一個(gè)可投入的事項(xiàng)（如股票）能得到多少回報(bào)，常常并不是事先能夠明確的;第二，回報(bào)不一定就是金錢，而其他方面（如愉快）常常很難量化，因而難以評(píng)估;第三，情勢(shì)是動(dòng)態(tài)變化的，還有機(jī)會(huì)成本的問題，今天決定投入（如時(shí)間）某事項(xiàng)了，就意味著明天可能難以改投更有意義的事項(xiàng)。

我們這里討論一種相對(duì)單純（但并不一定簡單）的情境，看算法能怎么發(fā)揮作用。

考慮一定量的資金n，要分配投入到m個(gè)不同的項(xiàng)目上，以獲得最大的回報(bào)。假設(shè)在每個(gè)項(xiàng)目上的投入和回報(bào)的對(duì)應(yīng)關(guān)系是預(yù)先知道的（如銀行定期存款的利息）。下面是一個(gè)具體的例子，假設(shè)你有n=5萬元錢，可以安排在m=3個(gè)項(xiàng)目上，表1給出不同的投資量分別可產(chǎn)生的回報(bào)。

你面對(duì)的問題就是，如何將5萬元錢分配到這3個(gè)項(xiàng)目上，讓總的回報(bào)最大。例如，若你把5萬元都投在項(xiàng)目1上，得到回報(bào)9，而你在項(xiàng)目1上投4萬，項(xiàng)目3上投1萬，得到回報(bào)7+3=10，就要好一些。是不是還有更好的呢？一般的問題就是，給定任意一個(gè)這樣的投資回報(bào)表，能否有一個(gè)系統(tǒng)化的方法（算法），求出最大回報(bào)，以及對(duì)應(yīng)最大回報(bào)的“投資組合”。

我們將從問題定義、求解思路、算法描述、算例分析和算法性質(zhì)這五個(gè)方面展開對(duì)這個(gè)問題的討論。這也是從算法角度進(jìn)行問題求解通常要考慮的幾個(gè)方面。

問題定義

給定總投資量n（整數(shù)）和m個(gè)單增項(xiàng)目回報(bào)函數(shù)[注]，fk（），k=1，2，…，m，要把n分成m份（整數(shù)），n1，n2，…，nm，其中nk≥0，滿足：

能夠看到，問題定義中強(qiáng)調(diào)了整數(shù)（按照問題背景，我們應(yīng)該理解為非負(fù)整數(shù)）和回報(bào)函數(shù)的單調(diào)性（嚴(yán)格講非減就可以了）。前者可以說主要是為了讓討論比較簡單，后者不僅是因?yàn)榫哂幸话阋饬x下的合理性，對(duì)算法設(shè)計(jì)的考慮也有某種關(guān)鍵性意義，將在算法性質(zhì)部分看到。

求解思路

談求解思路通常意味著某種方法論，即從哪個(gè)視角看待這個(gè)問題，入手去解決。下面介紹的，在計(jì)算機(jī)算法領(lǐng)域被稱為“動(dòng)態(tài)規(guī)劃”的方法，是算法設(shè)計(jì)的經(jīng)典技巧之一。

不妨先看看只有兩個(gè)項(xiàng)目可投資的情形，即m=2。如何確定最優(yōu)組合？無非就是要看下面這n+1種可能中哪一個(gè)最好：

注意，所有可能一共是n+1種，而不是n種。還要注意，相關(guān)的f1（n-k）和f2（k）都是已知的，即投資回報(bào)表給出的，于是我們有充分的基礎(chǔ)數(shù)據(jù)來用以得出結(jié)果。讓我們把這一結(jié)果記為F2（n）=max{f2（k）+f1（n-k），k=0，1，2…，n}，即兩個(gè)項(xiàng)目最優(yōu)投資組合的回報(bào)值。

如果有三個(gè)項(xiàng)目（m=3）的機(jī)會(huì)呢？那就可以看是否能通過給第三個(gè)項(xiàng)目也分配一些資金（k），剩下的（n-k）還是在前兩個(gè)項(xiàng)目中按照最優(yōu)的方式分，可以獲得更高的回報(bào)。如果用F2（n-k）表示投資量n-k在前兩個(gè)項(xiàng)目上分配能獲得的最大回報(bào)，也就是要看（注意f和F的區(qū)別）：

這n+1種情況中哪個(gè)最好？而其中的每一個(gè)F2（n-k）是我們已知怎么求的，即令式（2）中的n為這里的n-k。

這種想法可以推廣！一般地，用Fi-1（x）表示在i-1個(gè)項(xiàng)目上投資x的最優(yōu)回報(bào)，在i個(gè)項(xiàng)目上投資x的最優(yōu)回報(bào)Fi（x）就是下面x+1種可能中的最大值，fi（k）+Fi-1（x-k），k=0，1，2，…，x，記為：

其中，fi（k）是事先給定已知的。如何得知Fi-1（x-k）呢？這里呈現(xiàn)出一種“遞歸定義”的特征。我們可以想象將Fi-1（x-k）進(jìn)一步展開，直到i=2，F(xiàn)i-1（x-k）=F1（x-k）

=f1（x-k），也就是已知的。

在具體計(jì)算的時(shí)候，則是反過來——自底向上，從i=2開始，先算F2（x），x=0，1，…，n，再算F3（x），x=0，1，…，n，等等，直到Fm（n），就得到了我們要的結(jié)果。這里的要點(diǎn)是這些自底向上計(jì)算的中間結(jié)果過程Fi（x）都被記錄下來，直接用在后面的計(jì)算過程中，從而免去大量重復(fù)計(jì)算的開銷。

仔細(xì)體會(huì)上述過程，我們可以形象地感到是在從左到右填一張（n+1）行m列的表，表中要填的值就是Fi（x），x=0，1，2，…，n;i=1，2，…，m。當(dāng)計(jì)算Fi（x）的時(shí)候，要用到相應(yīng)單元的左鄰列的上半部單元的值，即Fi-1（0），F(xiàn)i-1（1），…Fi-1（x），如上頁表2中的指示框，還要用到式（4）中指出的fi（）。

這也就是“動(dòng)態(tài)規(guī)劃”方法的基本風(fēng)格，不少優(yōu)化問題的求解步驟都可以歸納為這個(gè)樣子，要領(lǐng)就是要從左到右、從上到下“填一張二維表”。表填完了，所需的結(jié)果就出現(xiàn)在表的右下角單元中。當(dāng)然，能這么做成功的條件是表最左邊的列和最上面的行的數(shù)據(jù)是已知的，也就是所謂“邊界條件”。

上述討論，指出了Fm（n），也就是表2右下角單元值的計(jì)算過程。這是否就完整解決了我們最初提的問題呢？還沒有！我們要的不僅是最大可能的回報(bào)值，還要一個(gè)具體的投資分配方案，它取得的回報(bào)是Fm（n）。如果只是算得一個(gè)數(shù)值Fm（n），具體該怎么投資還是不清楚。

這里涉及用算法來解決優(yōu)化方案設(shè)計(jì)中常見的一個(gè)挑戰(zhàn)。通常，問題的目標(biāo)是要得到一個(gè)優(yōu)化的設(shè)計(jì)，而不僅是表示設(shè)計(jì)優(yōu)化的量值。這就好比用導(dǎo)航軟件，僅僅告訴從A到B的最短路徑是10公里還不夠，我需要的是告訴我如何走，最后是10公里。

對(duì)于這樣的需求，通?？稍谇蟮米顑?yōu)值的過程中記錄一些關(guān)鍵性中間結(jié)果來滿足。那些中間結(jié)果幫助我們回過頭來構(gòu)建具體的優(yōu)化方案。對(duì)于本文討論的投資組合問題，如果在上述計(jì)算Fi（x）直到Fm（n）的過程中同時(shí)也記住形成Fi（x）時(shí)對(duì)應(yīng)在fi（）中的投資量，也就是在式（4）中取得最大值的k，就能夠讓我們?cè)谒愠鯢m（n）后逐步“回溯”得到對(duì)應(yīng)的投資方案。也就是說，在算法具體實(shí)施中我們面對(duì)的是如下頁表3所示的情境。與前面的表2相比，就是在每個(gè)Fi（x）旁伴隨了一個(gè)在項(xiàng)目i上的投資量K，它是0到x之中的一個(gè)數(shù)。該投資量是與投資項(xiàng)目i和當(dāng)前總投資量x相關(guān)的，我們用Ki（x）表示。算法實(shí)現(xiàn)中可以定義一個(gè)與Fi（x）結(jié)構(gòu)相同的數(shù)據(jù)結(jié)構(gòu)存放Ki（x），或?qū)⒃瓉淼谋砀衩恳涣袛U(kuò)展為兩列，分別存放Fi（x）和Ki（x），表3即為一個(gè)示意。其中每個(gè)數(shù)據(jù)單元中有兩個(gè)數(shù)[Fi（x），Ki（x）]。

這里，我們首先能認(rèn)識(shí)到的是，這樣的Ki（x）在按照式（4）計(jì)算Fi（x）的過程中“順手”就可以得到了，即對(duì)應(yīng)那個(gè)最大值的k。如何利用它們來構(gòu)造對(duì)應(yīng)Fm（n）的投資方案，將在下面的算法和例子中介紹。

算法描述

如前所述，對(duì)這種投資組合問題，算法分為兩個(gè)階段。第一階段是算得最終的優(yōu)化值，同時(shí)記住必要的中間結(jié)果;第二階段是基于第一階段的結(jié)果，構(gòu)造一個(gè)具體的優(yōu)化投資方案。于是我們的算法也分成如下兩段描述。

第一段是計(jì)算最優(yōu)回報(bào)，如上頁圖1所示;第二段是計(jì)算最優(yōu)組合，如上頁圖2所示。

第一段的第1、2行初始化Fi（0）=0，F(xiàn)1（x）=f1（x）， K1（x）=x，i=1，2…m;x=0，1…n，也就是那個(gè)二維表的第一列和第一行。隨后從左到右、從上到下逐個(gè)計(jì)算Fi（x）、Ki（x）。涉及三重循環(huán)，第一重循環(huán)投資項(xiàng)目數(shù)i從2到m，第二重循環(huán)總投資量x自1到n，第三重循環(huán)中k為投入到項(xiàng)目i的總量。計(jì)算Fi（x）需要從x+1個(gè)fi（k）+Fi-1（x-k）值中取最大的，對(duì)應(yīng)在項(xiàng)目i上的投資量k值存入Ki（x）。

算例分析

為了更好地說明問題，我們看一個(gè)稍微大一點(diǎn)的例子（取自參考文獻(xiàn)1），n=5，m=4。4個(gè)項(xiàng)目的回報(bào)函數(shù)（fi（x））如表4所示。

基于表4，運(yùn)行上述第一個(gè)算法（計(jì)算最優(yōu)投資回報(bào)），得到如表5所示的結(jié)果。

作為一個(gè)例子，我們來看對(duì)應(yīng)在前兩個(gè)項(xiàng)目上投資5的結(jié)果“F2（5）=26，K2（5）=4”是怎么得到的。為了得到F2（5），也就是要看在F1的基礎(chǔ)上，在第二個(gè)項(xiàng)目上的不同投資量會(huì)怎樣，即比較下面6個(gè)數(shù)：

其中26是最大的，而此時(shí)在第二個(gè)項(xiàng)目上投入4，即K2（5）=4。

我們看到，這個(gè)例子的最佳回報(bào)是61。如何能得到具體的投資方案呢？這就是上面第二階段算法（計(jì)算最優(yōu)組合）的作用。它做的是一個(gè)“倒推”。從最后的結(jié)果（61，1）中的1開始，它意味著要在項(xiàng)目4上投入1，于是在其他三個(gè)項(xiàng)目上的投資量就是5-1=4，其中分配在項(xiàng)目3上的投資量是K3（4）=3。那么在其他兩個(gè)項(xiàng)目的投資4-3=1，繼續(xù)回溯K2（1），為0，意味著在項(xiàng)目2投資為0。繼續(xù)回溯K1（1）=1，那么對(duì)應(yīng)項(xiàng)目1的投入是1萬。結(jié)論就是，給項(xiàng)目1投1萬，項(xiàng)目2不投，項(xiàng)目3投3萬，項(xiàng)目4投1萬，就能得到最高回報(bào)61。

算法性質(zhì)

我們關(guān)心正確性和效率兩個(gè)方面。

（1）這是一個(gè)正確的算法嗎？我們關(guān)心兩點(diǎn)，一是為什么算法結(jié)束時(shí)給出的Fm（n）的確就是在m個(gè)項(xiàng)目上投入n萬元的最優(yōu)投資組合的回報(bào)，即最大回報(bào)，二是為什么從記錄了[Fi（x），Ki（x）]的表中，結(jié)合給定數(shù)據(jù)fi（x），x=0，1，…，n;i=1，2，…，m，就能倒推出一種最優(yōu)投資組合。

對(duì)于第一點(diǎn)，關(guān)鍵是認(rèn)定公式（4）的正確性。可以這樣推理，即任何在i個(gè)項(xiàng)目上投資x的最優(yōu)組合，總可以表達(dá)為：

（5）其中ki=x。由于Fi（x）是最優(yōu)的，這個(gè)式子右邊的前i-1項(xiàng)加起來就必須是Fi-1（x-ki），即在i-1個(gè)項(xiàng)目上安排投資量x-ki能獲得的最佳回報(bào)，也就是Fi（x）=Fi-1（x-ki）+f（ki）。式（4）無非是說，既然Fi（x）一定是這個(gè)形式，那就看看所有這種表達(dá)式中哪一個(gè)取得最大值，我們就取它做Fi（x）！有了這個(gè)認(rèn)識(shí)再看算法，無非就是保證在按照式（4）計(jì)算每一個(gè)Fi（x）的時(shí)候，所需要的數(shù)據(jù)都已經(jīng)在前面準(zhǔn)備好了。表2數(shù)據(jù)項(xiàng)的填寫，按照從左到右、從上往下的次序來完成，就保證了這一點(diǎn)。

對(duì)于第二點(diǎn)，注意算法是從總投資量開始，倒序看應(yīng)該給每個(gè)項(xiàng)目安排多少資金。因?yàn)樵诘趇列記住了Ki（x），于是就知道了該給項(xiàng)目i安排的投資量。而從當(dāng)前投資量x中減去Ki（x），就是給前面i-1個(gè)項(xiàng)目安排的投資量。據(jù)此就可以定位到表中第i-1列的適當(dāng)?shù)男?，這就是從Ki倒推回Ki-1的根據(jù)。這個(gè)過程從i=m，x=n開始，直到i=2。在各項(xiàng)目上的投資量，就是一路上確定的那些K。算法正是這么做的。

這里，關(guān)于算法的第一階段有兩個(gè)進(jìn)一步的問題提請(qǐng)細(xì)心的讀者注意：第一是項(xiàng)目的順序，我們一直說“第一個(gè)項(xiàng)目”“前兩個(gè)項(xiàng)目”等，那么哪個(gè)項(xiàng)目算是第一個(gè)、第二個(gè)在此重要嗎？仔細(xì)體會(huì)上述式（5），會(huì)發(fā)現(xiàn)無關(guān)緊要。任何順序都會(huì)得到同樣的最終結(jié)果Fm（n），盡管中間的Fi（x）可能不一樣。第二是關(guān)于式（5）的條件中有“ki=x”。這意味著為了得到最大回報(bào)，一定要用完所有的投資。如果沒有回報(bào)函數(shù)單調(diào)增的假設(shè)，這還真不一定。

（2）這個(gè)算法的效率如何呢？注意到整個(gè)過程就是要計(jì)算Fi（x），i=2，3，…，m;x=1，2，…，n，即n行m-1列。而計(jì)算一個(gè)Fi（x）需要做x+1次比較，也就是說，計(jì)算一列數(shù)，F(xiàn)i（x），x=1，2，…，n，計(jì)算量為n（n+1）/2，于是整個(gè)計(jì)算復(fù)雜性就是O（m*n2/2）。

此時(shí)，比較一下蠻力法的效率會(huì)有意義。即根據(jù)問題的定義，給定正整數(shù)n，要把它分成m個(gè)非負(fù)整數(shù)，n1，n2，…，nm，nk≥0，滿足：

且要基于各個(gè)項(xiàng)目的回報(bào)函數(shù)，fi（），最大化總回報(bào)：

蠻力法就是枚舉每一個(gè)滿足（6）的解，帶入（7）得到對(duì)應(yīng)的值，留下最大的。這其中的計(jì)算量，正比于等式（6）的可行解的個(gè)數(shù)。組合數(shù)學(xué)告訴我們，它等于，大多數(shù)情況下要比m*n2/2大很多。