Dynamic Programming

Dynamic Programming

中文譯作「動態規劃」,英文常常縮寫成DP。在數學領域中,programming是指「最佳化(optimization)」的意思,例如求極大值、求極小值。dynamic是指「動態」的意思。顧名思義,Dynamic Programming是一個以動態的方式來進行最佳化的方法。

DP = Divide and Conquer + Memoization

DP可視做是Divide and Conquer的延伸版本。當運用Divide and Conquer所遞迴分割出來的子問題都非常相像的時候,並且當同樣的子問題一而再、再而三出現的時候──就運用Memoization儲存全部子問題的答案,節省重複計算相同問題的時間,以空間來換取時間。

由於全部子問題的答案都儲存在記憶體的緣故,計算答案的過程,就是反覆不斷地在各塊記憶體中讀取數據、計算數據、儲存數據,動感地達成最佳化──動態規劃之名由此而來。

出現過的子問題會被儲存

DP有一個特點,是當原問題題算好之後,其實也一併將所有出現過的子問題都算好了,其答案都可直接從表格存取。此後當重複提問類似問題時,若提問到的是這些子問題,就可直接從表格取得答案,不需再計算。

子問題可視做狀態,可嘗試建立狀態空間

當子問題之間非常相像的時候,不妨把子問題視作狀態。我們可以嘗試直接建立狀態空間,接下來才來觀察狀態們(子問題們)之間的關係,有助於找出原問題的遞迴分割方式。

時間複雜度、空間複雜度

由於問題的答案都在表格中,記憶體足夠的情況下,存取一個問題的答案通常只需O(1)。如果一個問題可以分成O(d)個子問題(一個問題的答案需要由O(d)個更小的問題計算而得),而全部的子問題共有O(n)個,時間複雜度就是O(n * d * 1)。

空間複雜度則必須以子問題們的出現期間來決定,在計算過程當中,已確定不再出現的子問題,就不必再儲存於表格中,記憶體就可以釋放,或者回收再利用,導致瞬間的記憶體用量不會太多,整體的空間複雜度就會降低。若只是單純的要儲存全部子問題,空間複雜度就是O(n)。

用Dynamic Programming設計演算法時的步驟

1. 利用Divide and Conquer把原問題遞迴地分成許多更小的問題。(recurrence)
	甲、子問題與原問題的求解方式皆類似。(optimal sub-structure)
	乙、子問題會一而再、再而三的出現。(overlapping sub-problems)
2. 確認每個問題需要哪些子問題來計算答案,並確認總共有哪些子問題。(state space)
3. 決定各個問題的計算先後次序。(computational sequence)
4. 安排好各個問題的答案,要存放在表格的哪個位置。(lookup table)
5. 實做程式,主要有兩種方式:
	甲、Top-down, Recursive.
	乙、Bottom-up, Iterative.

第一點。先找到原問題和其子問題們之間的關係,寫出遞迴公式。如此一來,便可利用遞迴公式,用子子問題的答案,求出子問題的答案;用子問題的答案,求出原問題的答案。

第二點,確認可能出現的子問題全部共有哪些,這樣才能知道要計算哪些子問題,才能知道共會花多少時間、多少記憶體。

第三點。有了遞迴公式和表格結構之後,就必須安排出一套計算的順序。大問題的答案,總是以小問題的答案來求得的,所以,小問題的答案是必須先算的,否則大問題的答案從何而來呢?

我們會利用較小問題的答案,計算出較大問題的答案──因此,一個好的安排方式,不但會使程式碼容易撰寫,還可有效節省記憶體空間,甚至重複利用記憶體空間。

第四點。實作DP的程式時,會建立一個表格,在表格存入所有大小問題的答案。安排好每個問題的答案在表格的哪個位置,這樣計算時才能知道該在哪裡取值。這個表格其實就是所謂的lookup table。

當撰寫程式碼的時候,應小心下面幾項問題:

初始值:記得先將最小、最先被計算的子問題,將其答案預先算好,內建於程式碼中,並存入表格。一道遞迴公式必須擁有初始值,才有辦法計算其他項。

表格界限:切勿存取超出表格界限的地方。計算過程中,一旦子問題的答案出錯,就會如骨牌效應般一個影響一個,造成很難除錯。

計算順序:切勿存取還沒計算過答案的子問題,原因同前項所述。

第五點。留待下述範例解釋。

一、recurrence

以下以著名的爬樓梯問題來做為範例,其遞迴公式如下:

f(n) =
 { 1                , if n = 0
 { 1                , if n = 1
 { f(n-1) + f(n-2)  , if n >= 2

註:為了寫作程式方便,遞迴公式中設計了n=0的情形。

為了讓程式碼比較好寫,設計遞迴公式時,可以嘗試在不與原本公式起衝突的情況下,額外增加一些邊界條件。

二、state space

全部的子問題共有六個,從「爬完零階」到「爬完五階」。每個子問題的答案都是由前兩階的答案求得,除了「爬完零階」與「爬完一階」以外。

三、computational sequence

必須最先計算,也是最小的子問題是「爬完零階」與「爬完一階」,它們都是寫程式時就能夠內建答案的子問題。

剩下的子問題,都必須先算好階數少一階、階數少二階這兩個子問題,所以必須由階數較小的子問題開始算。

必須最後計算,也是最大的子問題是原問題「爬完五階」。

整體的計算順序是:「爬完零階」、「爬完一階」、「爬完兩階」、「爬完三階」、「爬完四階」、「爬完五階」。

四、lookup table

可以簡單用一條六格的一維陣列做為lookup table,每一格都對應到一個問題的答案。

然後設定好最小的子問題的答案,「爬完零階」與「爬完一階」。

五、實做程式

直接用遞迴實作,而不使用記憶體儲存各個問題的答案,是最直接的方式,也是最慢的方式。時間複雜度是O(f(n))。有些問題一而再、再而三的出現,不斷呼叫同樣的函式,效率不彰。很多剛接觸DP的新手都會犯這種錯誤。

正確的DP,是一邊計算,一邊將計算出來的數值存入表格當中,以後便不必再重算。這裡整理了兩種實做方式:

1. Top-down, Recursive.
2. Bottom-up, Iterative.

這兩種方式各有優缺點,以下說明這兩種方式有何不同。

五之一、Top-down, Recursive

第一種。採用Divide and Conquer的遞迴實作方式,以Divide階段分割原問題,並以Merge階段來計算出原問題的答案。每當計算出一個問題的答案後,就馬上儲存在表格裡面,並記錄該問題已計算。

這個方式的好處是不必斤斤計較計算順序,因為程式碼中的遞迴結構會迫使最小的子問題先被計算。這個方式的另一個好處是只計算必要的子問題,而不必計算所有可能的子問題(計算整個狀態空間)。

這個方式的壞處是程式碼採用遞迴結構,不斷呼叫函式,執行效率較差。這個方式的另一個壞處是無法自由地控制計算順序,因而無法妥善運用記憶體,浪費了可回收再利用的記憶體。

五之二、Bottom-up, Iterative

第二種。訂定一個計算順序,然後由最小的子問題先計算,其特色是程式碼通常只有幾個迴圈。這個方式的好處與壞處恰與前一個方式互補。

總結

現在已經有許多問題已經發掘出DP的解法,這些問題通常以遞迴公式和表格結構的樣式,做為主要的分類依據。有賴前人辛苦耕耘,近年來已漸漸整理出幾個經典的題型了。學習這些題型,可以增廣解題的思考方向。大家在學習之餘,也不妨順便開創一些新題型,可供後人學習!這裡列出一些常見的簡易題型,供各位牛刀小試。

UVa 369 485 495 623 10334 10446 10520

Staircase Walk

Staircase Walk

有一個長方形的方格棋盤,從左上角開始,欲走至右下角,每次只能往右走一格或者往下走一格。請問有幾種不同走法?

這個問題可以很容易的找到遞迴公式。對某個位置的方格來說,只可能是從左走來或者從上走來,將這兩種情形分開,便得到遞迴公式:

c(i, j) =
 { 0                         , if i < 0 or j < 0
 { 1                         , if i = 0 or j = 0
 { c(i-1, j) + c(i, j-1)     , if i > 0 and j > 0

c(i, j):從格子 (0, 0) 走到格子 (i, j) 的走法種類數。

除了遞迴公式之外,這個問題也有一般公式解:http://mathworld.wolfram.com/StaircaseWalk.html

時間複雜度分析:令X和Y分別是棋盤的長和寬。每個子問題用O(1)時間(用兩個子問題)就可算得,共有X*Y個子問題,所以算出所有子問題要用O(XY)時間。

空間複雜度分析:共有X*Y個子問題,所以要用O(XY)空間,簡單來說就是開一個二維陣列啦!如果不需要紀錄所有子問題的答案,只想算出其中一個子問題,那只需要一條一維陣列就可以了,也就是O(min(X, Y))空間。

程式碼就不提供囉!各位可以自己試試看!

如果某些格子上有障礙物呢?其實也很簡單,如果某格有障礙物,就把此格的c(i, j)設為零就可以了。

如果也可以往右下斜角走呢?那麼遞迴公式就再修改一下,多加一項c(i-1, j-1)就行了。

如果可以往上下左右走呢?那麼就可以不斷繞圈子,走法就成了無限多種了。寫成遞迴公式的話,就會產生無窮遞迴,永遠也不會結束。

如果也可以往右上斜角走呢?因為不會產生無窮遞迴,所以這是可以解的!

UVa 10599

Maximum Subarray

Maximum Subarray
(Maximum Consecutive Sum)
(Maximum Consecutive Subsequence)

問題:從一串數列中取一連串數字求其總和。找出最大的總和。最糟糕的情況就是什麼數字都不取,總和為零。

如果用窮舉法的話,窮舉所有可能的起點、終點,並計算總和,時間複雜度就是O(N^3)。

這是一個非常簡單的問題,只要依序累加數字、做點判斷,就可以找到答案。累加數字求總和就是種Dynamic Programming!

更詳細的資料,可參考「名題精選百則」這本書。現在直接來看程式碼吧。

計算Maximum Subarray之元素總和

時間複雜度是O(N)。

找出Maximum Subarray的位置

當然也可以找出那串數字。如果有很多串,下面這支程式碼只會找出比較早出現的那一串。

計算Maximum Subarray之元素總和(至少取一個數字)

推廣

這個問題還可推廣到2D、3D。時間複雜度分別是O(N^3)、O(N^5)。以下直接提供3D的情形。

最後,來一點練習題目吧。

UVa 507 10684 108 836 10827 10755

0/1 Knapsack Problem之一

Knapsack Problem

問題:將一群物品儘量塞進背包裡,令背包裡物品總價值最高。僅考慮背包只有負重限制(似乎太天真了一點)。

關於背包問題,世界上已經有很多研究成果了。這裡向大家提供一本專述背包問題的論著,作者精心整理了背包問題的相關問題和研究成果,並免費提供電子檔給大家,大家請記得要滿懷感激的看此書:http://www.or.deis.unibo.it/knapsack.html

UVa 233 10898

0/1 Knapsack Problem

背包問題是很經典的問題,亦引申出許多變形和應用。這裡我們只介紹最基本易懂的其中一種變形:0/1 knapsack problem。

文言的說法是:每種類型的物品只會放進背包零個或一個。通俗的說法是:每個物品都是不同類型的,每種物品都只有一個。

這個問題原本是個NP-Complete問題。當數值範圍不大時,能以DP處理之。

分割問題的方法

當我們把一件物品放進背包裡時,會讓總價值變高,並且讓背包變重。對某一件物品來說,我們可以選擇放或不放;然後移去這件物品所帶來的影響,將問題縮小成子問題。遞迴式便可設計為:

c(n, w) = max( c(n-1, w), c(n-1, w-W[n]) + C[n] )
               ^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^^
               不放 -> 0         放 -> 1

n:第1個到第n個物品要放進背包內。
w:背包負重上限。
c(n, w):第1個到第n個物品儘量塞入負重限制為w的背包時,其總價值的最大值。
W[n]:第n個物品的重量。
C[n]:第n個物品的價值。

考慮一下東西放不進去時的情形,以及沒有東西時的情形。

c(n, w) =
 { 0                                        , if n = 0 and w >= 0
 { max( c(n-1, w), c(n-1, w-W[n]) + C[n] )  , if n > 0 and w-W[n] >= 0
 { c(n-1, w)                                , if n > 0 and w-W[n] < 0

物品一開始的先後順序是無所謂的,最後得出的答案都會一樣。

計算出背包裡物品總價值的最大值(Bottom-up)

只要計算所有小問題,那麼大問題的答案必然可以推得出來。建立二維表格後,依序計算每個小問題吧!

因為計算時只需要用到上方和左上方的格子,所以其實只需要一條陣列就夠了。不過計算次序需要改為由陣列後端開始,才不會覆蓋掉需要拿來計算的陣列格子。

程式碼也可以寫成這樣,讓人容易理解。

計算出背包裡物品總價值的最大值(Top-down)

方才所採用的方法會計算到所有可能的小問題,然而並不是所有小問題都需要計算,故採用Top-down的方式會比較快。

找出此時背包裡最多可剩下多少空間、最少只用了多少空間

從表格的右方開始往左搜尋即可。當發現最佳的cost將要變小時,表示該處為最節省空間的地方。然而這不是很好的作法。

找出此時背包裡放了哪些物品

另外再建立一個二維陣列,紀錄每一格的數值是由哪個子問題所算得的。每個問題只會有放或不放兩種情形,所以只要記錄放或不放便可以了。這段程式碼只能找出其中一種配置物品的方式。

這裡要注意的是,由於尋找放入的物品時必須要從表格的右下角逆推,如此得到的物品順序並不會是字典順序最小的一組。因此下面的程式碼會將所有物品依照相反順序進行DP的計算,然後再逆推、求放入的物品時,就會剛好是字典順序了。

找出所有的配置物品的方式

方才的程式碼只能找出一種配置背包內物品的方式。若要找出所有方式,那就要寫個遞迴了吧?就我所知,目前尚未存在有效率的方法,能夠求出所有的配置方式。

塞入最少個物品、最多個物品

若只是要找出物品塞最少個或最多個的配置方式,則可以重新設計recurrence為:

c(n, w, t) = max( c(n-1, w-W[n], t-1) + C[n] , c(n-1, w, t) )

t:放入的物品個數。

建立三維的表格,並算出每一格的答案後,接著窮舉所有可能的t,觀察那些格子、相互比較cost之後,便可以得到最佳解。程式碼就不寫了。

Greedy

當每個物品的重量相互之間皆為倍數關係,優先放入價值與重量比值較高的物品,可以讓總價值最高。但是我不確定是不是一定要呈倍數關係,才能有greedy演算法。(可參考本站文件「Dynamic Programming─Money Changing Problem」的Change-Making Problem: Cashier's Algorithm章節)

計算出背包裡物品總價值的最小值

剛剛所討論是讓背包裡物品總價值最高的方法;至於要讓背包裡物品總價值最低的話,那就是什麼東西都不要放進背包了吧。

整理了一些類題。

UVa 431 624 990 10130 10819

0/1 Knapsack Problem之二

另一種分割問題的方法

想像物品放入背包時是照物品編號順序來放。由於每一種物品都可能是最後一個放入背包的物品,遞迴式可設計為:

c(n, w) = max(	0,                           都不放
		c(0, w-W[0]) + C[0],         最後是放第1個物品(index 0)
		c(1, w-W[1]) + C[1],         最後是放第2個物品(index 1)
		... ,                        ...
		c(n-1, w-W[n-1]) + C[n-1] )  最後是放第n個物品(index n-1)

n:第1個到第n個物品要放進背包內。
w:背包負重上限。
c(n, w):n個物品儘量塞入負重限制為w的背包時,其總價值的最大值。
W[n]:第n個物品的重量。
C[n]:第n個物品的價值。

計算出背包裡物品總價值的最大值(Top-down)

隨意寫一下。如果寫錯要跟我講呀。

Matrix Chain Multiplication

Matrix Chain Multiplication

矩陣乘法具有結合率。在一連串的矩陣乘法中,可以從中任取兩個相鄰的矩陣相乘,先行結合成一個新矩陣,也不會改變所有矩陣相乘之後的結果。

在一連串的矩陣乘法中,無論從何處開始相乘其結果都不變,然而計算速度卻有差異。兩個矩陣大小為a x b及b x c,其相乘需要O(a*b*c)的時間(當然還可以更快,但此處不討論),那麼一連串的矩陣乘法,需要多少時間呢?

分割問題的方法

這個問題在許多地方都找得到資料,故只略述。從最後一次相乘的角度來看,原來的一連串矩陣,可從最後一次相乘的地方分開,便能將原問題化作兩串矩陣相乘,然後再合併起來。分割問題的方法類似於本站文件「Divide and Conquer─Fast Exponentiation」,但在本問題中,並非固定地對半分,而是同時考慮所有可能的分法。

當然也可以印出矩陣相乘的順序。只要另外再用一個陣列來紀錄每次相乘的位置就行了。

另一種方法

現今已能在O(NlogN)時間內解決Matrix Chain Multiplication,是我從網路論壇上聽聞到的:http://historical.ncstrl.org/litesite-data/stan/CS-TR-81-875.pdf

UVa 348 442

Optimal Binary Search Tree

Optimal Binary Search Tree

問題說明:略!總之就是所有鍵值的「深度」乘上「權重(出現頻率)」的總和要最小。

Optimal Binary Search Tree的相似產物

這裡整理了三種很相像的樹,都是令所有鍵值的「深度」乘上「權重(出現頻率)」的總和最小。

Optimal Binary Search Tree:樹上所有點都是鍵值,且鍵值須照大小順序安排。可用Dynamic Programming解決,時間複雜度為O(N^3),可優化至O(N^2)。

Optimal Alphabetic Binary Code Tree:只有葉子是鍵值,且鍵值前後順序需固定。可用Greedy解決,時間複雜度為O(NlogN)。

Optimal Binary Code Tree(Huffman Tree):只有葉子是鍵值,且鍵值順序隨意。可用Greedy解決,時間複雜度為O(NlogN)。

分割問題的方法

和Matrix Chain Multiplication相同,窮舉所有可以當作root的鍵值,並以root將原來的樹分作左右兩棵子樹,便縮小了問題。

實作

下面的程式碼將陣列邊界左右各加一格,如此可省去一些判斷陣列邊界的麻煩。

由於第二層迴圈實行時,sum[j][j+i]都維持定值,也不影響最大值的判斷,故可將之移到迴圈外面去。加法次數減少,會稍微快一點。

迴圈判斷式中,關於區間起點的範圍,與其用減法計算區點起點的界限,不如簡單想成區間終點不超過陣列邊界。

印出Optimal Binary Search Tree

嗯哼。為了不剝奪各位寫程式的樂趣,所以這裡就不提了。

時間複雜度

所有的子問題共有O(N^2)個,每個子問題需要窮舉O(N)種分割點,故時間複雜度為O(N^3)。

優化

當recurrence具有特殊的遞增或遞減性質時,便可有辦法加速。【待補凸四邊形不等式】

每次計算一個子問題時,總是要窮舉所有的分割點。然而有些分割點很明顯地是錯誤的,尤其是靠近區間邊界的那些分割點,實在不太可能將兩顆子樹分的夠均勻、令總和最小。

另外這個問題還有一個特性。相近的子問題,其分割點的位置也很相近。例如子問題[a,b]的分割點,應該會與子問題[a-1,b]、[a+1,b]的分割點差不多,因為分割出來的左右子樹頂多也只差了一個鍵值,考量到左右子樹要均勻才行,可推論總成本、子樹的形狀、分割點的位置應該都是差不多的。

事實上,細心的觀察者們,可以發現子問題[a,b]的分割點,必定位於更小的子問題[a+1,b]和[a,b-1]的分割點之間。如此一來,每次計算一個子問題時,就不必窮舉所有的分割點,只要找更小的子問題[a+1,b]和[a,b-1]的分割點之間的分割點即可,為常數個(請各位自行觀察一下)。

由於檢查分割點的次數變成常數次,所以時間複雜度為O(1)。計算O(N^2)個子問題時,時間複雜度就是O(N^2)了。

UVa 10304

Bitmask in Dynamic Programming問題特輯

Bitmask

bitmask是一串二進位數字,每一個位元分別代表一件東西,1代表開啟,0代表關閉。例如現在有十個燈泡,編號設定為零到九,其中第零個、第一個、第四個、第八個燈泡是亮的,剩下來的燈泡是暗的,我們可以用一個10 bit的二進位數字0100001001,來表示這十個燈泡現在的亮暗狀態。

如果想替各種狀態做進一步的記錄,我們可以建立一個大小為2^10的陣列,便囊括了所有可能的狀態。這個陣列的每一格,就代表一種燈泡開關的狀態,可以進行記錄。

Maximum Cardinality Matching

大意:給一張圖,相鄰的兩點可匹配在一起,求這張圖的最大匹配方式及匹配數目。

此題有多項式時間的解法,不過很難實作。用DP雖然慢了些,但簡單多了,只要把一對匹配在一起的點拿掉,就可以得到遞迴公式:

c[s] = max ( c[s-{i}-{j}] + adj[i,j] )

c[s+{i}+{j}] = max ( c[s] + adj[i,j] )

i、j:點。
s:點集合。
c[s]:s當中的點,所構成的最大匹配數。
adj[i,j]:adjacency matrix。邊ij暢通就是1,不暢通就是0。

實作時,可利用bitmask做為s的資料結構,匹配過的點都標成1,未匹配的點都標成0。

這個方法的時間複雜度為O(2^N * N^2),空間複雜度為O(2^N)。

這個方法需要大量記憶體,所以無法計算N很大的情況,何況編譯器也不准我們開太大的陣列,N=28就是極限了。這個方法同時也需要大量時間,以現在的個人電腦來說,N=17就已經要花上幾分鐘才能求出答案了。

這個演算法可以再修正,讓時間複雜度成為O(2^N * N),各位可以試試看。

Minimum Weight Matching / Maximum Weight Matching

大意:給一張圖,相鄰的兩點可匹配在一起,求這張圖的所有最大匹配當中,權重最小(大)的匹配方式及權重。

此題亦有多項式時間的解法,但是很難實作。DP解法同前,稍微改一下遞迴公式的運算符號就行了。程式碼就不寫了。

w[s] = min ( w[s-{i}-{j}] + adj[i,j] )

w[s+{i}+{j}] = min ( w[s] + adj[i,j] )

i、j:點。
s:點集合。
w[s]:s當中的點,所構成的最大匹配的最小權重。
adj[i,j]:adjacency matrix。邊ij的權重。

UVa 10888 10911 11439

Chinese Postman Problem(CPP)

大意:給定一張圖,郵差想走過圖上每一條邊去寄信,最後回到原點。求最短的走法及長度。

此題會用到Minimum Weight Matching,故在此列出。此題不論是無向圖或是有向圖,都有多項式時間的解法,可是很難實作。

UVa 10296 11156

判斷一張圖上存不存在Hamilton Path

大意:是否存在一條通過圖上所有點的路徑,若有則找出走法。

此題目前無多項式時間的解法。最容易的解法是使用backtracking,窮舉圖上所有點的各種排列方式,一種排列方式當作是一條路徑,並判斷該路徑是不是Hamilton Path。

把一條路徑的最後一條邊拆掉的話,就可以形成遞迴公式。注意到路徑的端點,當端點不同,結果會不同,所以需要另外一個維度來記錄路徑的端點:

path[s,j] = or_all ( path[s-{j},i] && adj[i,j] )

path[s+{j},j] = or_all ( path[s,i] && adj[i,j] )

i、j:點。
s:點集合。
path[s,j]:經過s當中所有點且最後一點是j的路徑,如果暢通就是true,不暢通就是false。
adj[i,j]:adjacency matrix。邊ij暢通就是true,不暢通就是false。

計算一張圖的Hamilton Path的數量

解法同前,稍微改一下遞迴公式的運算符號就行了。程式碼就不寫了。

c[s,j] = sigma ( c[s-{j},i] * adj[i,j] )

c[s+{j},j] = sigma ( c[s,i] * adj[i,j] )

i、j:點。
s:點集合。
c[s,j]:經過s當中所有點且最後一點是j的路徑數量。
adj[i,j]:adjacency matrix。邊ij暢通就是1,不暢通就是0。

Travelling Salesman Problem(TSP)

TSP是一個經典的NP-Complete問題。大意是:一個周遊各國的商人,他想去所有不同的城市買賣東西。商人為了節省車馬費,打算從其中一個城市出發,各個地方剛好經過一次之後,回到原城市。所有城市之間都有路,請規劃出距離最短的路線,以及算出距離。這個問題其實也就是找一個權重最小的Hamilton Circuit。

解法同前,稍微改一下遞迴公式運算符號就行了:

dist[s,j] = min ( dist[s-{j},i] + adj[i,j] )

dist[s+{j},j] = min ( dist[s,i] + adj[i,j] )

i、j:點。
s:點集合。
dist[s,j]:經過s當中所有點且最後一點是j的路徑長度。
adj[i,j]:adjacency matrix。邊ij的長度。

上面的遞迴公式只能求出權重最小的Hamilton Path。在TSP當中,不管從哪一點出發,求出來的答案都一樣,反正都會繞一圈經過每個點,所以我們令商人從第0點出發,當找到一條Hamilton Path之後,再額外加上一條回到第0點的邊,就能產生一個Hamilton Circuit了。

另外這裡再附上一個不正確的程式碼。表格的用途是這樣的:dp[目前走過的地點數][已走過的地點]。這個方法會在計算dp[N][N個1組成的二進位數字]的時候產生錯誤(N為地點數目)。

UVa 216 10068 10496 10818 10937 10944 10605 10890

Subset Sum Problem / Partition Problem

參照Money Changing Problem之湊得某個價位的錢幣用量有哪幾種。

【尚待整理】

UVa 242 10032 10690 10930