李曉明

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

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

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

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

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

問題定義

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

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

求解思路

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

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

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

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

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

這種想法可以推廣！一般地，用Fi-1（x）表示在i-1個項目上投資x的最優(yōu)回報，在i個項目上投資x的最優(yōu)回報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），也就是已知的。

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

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

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

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

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

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

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

算法描述

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

第一段是計算最優(yōu)回報，如上頁圖1所示;第二段是計算最優(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，也就是那個二維表的第一列和第一行。隨后從左到右、從上到下逐個計算Fi（x）、Ki（x）。涉及三重循環(huán)，第一重循環(huán)投資項目數(shù)i從2到m，第二重循環(huán)總投資量x自1到n，第三重循環(huán)中k為投入到項目i的總量。計算Fi（x）需要從x+1個fi（k）+Fi-1（x-k）值中取最大的，對應(yīng)在項目i上的投資量k值存入Ki（x）。

算例分析

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

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

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

其中26是最大的，而此時在第二個項目上投入4，即K2（5）=4。

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

算法性質(zhì)

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

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

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

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

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

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

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

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

且要基于各個項目的回報函數(shù)，fi（），最大化總回報：

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