學習安排（8月27日-8月28日）
1.主要學習視頻Week9&期末考試
鏈接（http://www.xuetangx.com/courses/MITx/6_00_2x/2014_T2/courseware/d39541ec36564a88af34d319a2f16bd7/）
2.參考書第13章動態(tài)規(guī)劃
動態(tài)規(guī)劃是一種非常高效的方法，適用于解決具有重復子問題和最優(yōu)子結(jié)構(gòu)的問題。
- 如果一個問題的全局最優(yōu)解可以通過組合局部子問題的最優(yōu)解求出顷锰，那么這個問題就具有最優(yōu)子結(jié)構(gòu)。我們已經(jīng)見過一些這樣的問題嚼蚀，比如歸并排序。歸并排序?qū)σ粋€列表進行排序的方式就是先對子列表進行排序，然后再合并子列表的排序結(jié)果。
- 如果求出一個問題的最優(yōu)解時需要對同樣的某個問題求解多次拾酝，那么這個問題就具有重疊子
問題。
0/1背包問題具有這兩個特性卡者，盡管不太明顯蒿囤。我們要先看一個更明顯具有最優(yōu)子結(jié)構(gòu)和重疊子問題的問題。
又見斐波那契數(shù)列
之前我們介紹了一個很直觀的斐波那契數(shù)列的遞歸實現(xiàn)：
def fib(n):
"""假設n是非負整數(shù)
返回第n個斐波那契數(shù)"""
if n == 0 or n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
雖然這個遞歸實現(xiàn)是正確的虎眨，但效率太差蟋软。復雜度的增長與函數(shù)結(jié)果的增長成正比镶摘，而斐波那契數(shù)列的增長速度非乘宰快。舉例來說凄敢，fib(120)是8 670 007 398 507 948 658 051 921碌冶。如果每次遞歸調(diào)用需要1納秒，那么fib(120)需要250 000年才能結(jié)束涝缝。fib函數(shù)只有寥寥幾行代碼扑庞，很明顯問題出在fib函數(shù)調(diào)用自己的次數(shù)上譬重。舉個例子，我們看一下fib(6)的調(diào)用樹：
請注意罐氨，我們在一遍又一遍地計算同一個值臀规。例如，fib(3)被調(diào)用了3次栅隐，而且每一次調(diào)用又引發(fā)了對fib函數(shù)的另外4次調(diào)用塔嬉。很容易就能想到，可以將fib函數(shù)的第一次調(diào)用結(jié)果保存下來租悄，然后在需要的時候直接查找谨究，而不是重新計算。這種方法稱為備忘錄法泣棋，是動態(tài)規(guī)劃的核心思想胶哲。
下面給出了一個基于備忘錄法的斐波那契函數(shù)的具體實現(xiàn)。函數(shù)fastFib中有一個參數(shù)memo潭辈，用來記錄已經(jīng)計算過的函數(shù)值鸯屿，這個參數(shù)的默認值是一個空字典。當使用一個大于1的整數(shù)n調(diào)用fastFib時把敢，fastFib會先在memo中尋找n碾盟，如果沒有找到（因為這時是第一次使用這個值調(diào)用fastFib），就會拋出一個異常技竟。此時冰肴，fastFib就使用標準的斐波那契遞推公式，并將結(jié)果保存在memo中榔组。
def fastFib(n, memo = {}):
"""假設n是非負整數(shù)熙尉，memo只進行遞歸調(diào)用 返回第n個斐波那契數(shù)"""
if n == 0 or n == 1:
return 1
try:
return memo[n]
except KeyError:
result = fastFib(n-1, memo) + fastFib(n-2, memo)
memo[n] = result
return result
動態(tài)規(guī)劃與0/1 背包問題
我們介紹過一種最優(yōu)化問題，即0/1背包問題搓扯〖焯担回憶一下，我們介紹了一種復雜度為O(nlog(n))的貪婪算法锨推，但這種算法不能保證找到最優(yōu)解铅歼。除此之外，我們還介紹了一種可以保證找到最優(yōu)解的暴力算法换可，但運行時間是指數(shù)增長的椎椰。動態(tài)規(guī)劃可以提供一種實用的方法，在合理的時間內(nèi)解決大部分0/1背包問題沾鳄。作為推導解決方案的第一步慨飘，我們先基于窮舉法得到一個指數(shù)級別的解法。核心思想就是構(gòu)造一個根二叉樹，枚舉所有滿足重量約束的狀態(tài)瓤的，從而探索可行解空間休弃。
在0/1背包問題的搜索樹中，每個節(jié)點都使用一個四元組進行標注圈膏，這個四元組表示的是這種背包問題的一個局部解塔猾。四元組中的四個元素如下：
- 要帶走的物品集合；
- 還沒有決定是否要帶走的物品列表稽坤；
- 要帶走的物品集合中的物品總價值（這個值只是為了優(yōu)化算法桥帆，因為可以從集合中計算出這個值）；
- 背包的剩余空間（這也同樣是一種算法優(yōu)化方式慎皱，因為這個值可以通過背包允許的總重量減去當前要帶走的物品總重量計算出來）老虫。
這個樹是從根節(jié)點開始，自頂向下地構(gòu)建出來的茫多。我們從待定物品中選擇出一個祈匙，如果背包放得下這個物品，就建立一個節(jié)點天揖，反映出選擇帶走這個物品的后果夺欲。按照慣例，我們將這個節(jié)點作為左子節(jié)點今膊，而用右子節(jié)點表示不帶走這個物品的后果些阅。以遞歸方式不斷執(zhí)行這個過程，直到背包被裝滿或者沒有待定物品斑唬。因為每條邊都表示一個決策（帶走或不帶走某個物品）市埋，所以這種樹稱為決策樹。
如下是一個表示物品集合的表格恕刘。
| 名稱 | 值 | 重量 |
|---|---|---|
| a | 6 | 3 |
| b | 7 | 3 |
| c | 8 | 2 |
| d | 9 | 5 |
給出一個決策樹缤谎，在背包能夠容納的最大重量為5的假設之下，可以確定應該帶走哪些物品褐着。樹的根節(jié)點（節(jié)點0）有一個標簽<{}, [a, b, c, d], 0, 5>坷澡，表示沒有選擇物品，所有物品都處于待定狀態(tài)含蓉，帶走的物品總值為0频敛，背包剩余空間還能容納的重量為5。節(jié)點1表示物品a被帶走馅扣，物品[b, c, d]處于待定狀態(tài)斟赚，帶走的物品總值為6，背包還能容納2的重量岂嗓。節(jié)點1沒有左子節(jié)點汁展，因為物品b的重量為3，不能放在背包中厌殉。
對于每個葉節(jié)點食绿，或者第二個元素為空列表（表示沒有物品可以考慮是否帶走），或者第四個元素為0（表示背包中已經(jīng)沒有剩余空間）公罕。這種深度優(yōu)先的樹搜索使用遞歸實現(xiàn)如下器紧。
def maxVal(toConsider, avail):
"""假設toConsider是一個物品列表，avail表示重量
返回一個元組表示0/1背包問題的解楼眷，包括物品總價值和物品列表"""
if toConsider == [] or avail == 0:
result = (0, ())
elif toConsider[0].getWeight() > avail:
#探索右側(cè)分支
result = maxVal(toConsider[1:], avail)
else:
nextItem = toConsider[0]
#探索左側(cè)分支
withVal, withToTake = maxVal(toConsider[1:],
avail - nextItem.getWeight())
withVal += nextItem.getValue()
#探索右側(cè)分支
withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
#選擇更好的分支
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
return result
程序中是否還有重疊子問題呢铲汪？乍一看似乎沒有。在樹的每一層罐柳，我們考慮的都是不同的可用物品集合掌腰，這說明如果確實存在普通的重疊子問題，那么它們一定在樹的同一層张吉。實際上齿梁，同一層的每個節(jié)點的待定物品集合確實是一樣的。不過肮蛹，從圖13-4中的標注可以看出勺择，某層的每一個節(jié)點的待定物品集合和更高層中節(jié)點的待定物品集合是不同的。
考慮一下每個節(jié)點需要解決的問題伦忠。這個的問題就是省核，在給定剩余可用重量的情況下，從待定物品集中找到一個最優(yōu)的物品昆码。決定剩余可用重量的不是帶走的具體物品或帶走的物品的總價值气忠，而是帶走的物品的總重量。所以赋咽，舉例來說笔刹，在決策樹圖中，節(jié)點2和節(jié)點7要解決的實際上是同一個問題：在給定剩余可用重量為2的情況下冬耿，確定待定物品集合[c, d]中應該帶走哪個物品舌菜。
下面的代碼利用最優(yōu)子結(jié)構(gòu)和重疊子問題，為0/1背包問題提供了一個動態(tài)規(guī)劃解決方案亦镶。通過添加一個附加參數(shù)memo日月，記錄已經(jīng)解決的子問題的解。memo是使用字典實現(xiàn)的缤骨，它的鍵由toConsider的長度和剩余可用重量構(gòu)成爱咬。表達式len(toConsider)是待定物品集合的一種簡潔表示，可以這樣表示的原因是物品總是從列表toConsider的同一端（前端）被移除绊起。
def fastMaxVal(toConsider, avail, memo = {}):
"""假設toConsider是物品列表精拟，avail表示重量memo進行遞歸調(diào)用
返回一個元組表示0/1背包問題的解，包括物品總價值和物品列表"""
if (len(toConsider), avail) in memo:
result = memo[(len(toConsider), avail)]
elif toConsider == [] or avail == 0:
result = (0, ())
elif toConsider[0].getWeight() > avail:
#探索右側(cè)分支
result = fastMaxVal(toConsider[1:], avail, memo)
else:
nextItem = toConsider[0]
#探索左側(cè)分支
withVal, withToTake =\
fastMaxVal(toConsider[1:],
avail - nextItem.getWeight(), memo)
withVal += nextItem.getValue()
#探索右側(cè)分支
withoutVal, withoutToTake = fastMaxVal(toConsider[1:],
avail, memo)
#選擇更好的分支
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
memo[(len(toConsider), avail)] = result
return result
