學(xué)習(xí)安排（8月27日-8月28日）
1.主要學(xué)習(xí)視頻Week9&期末考試
鏈接（http://www.xuetangx.com/courses/MITx/6_00_2x/2014_T2/courseware/d39541ec36564a88af34d319a2f16bd7/）
2.參考書第13章動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃是一種非常高效的方法，適用于解決具有重復(fù)子問題和最優(yōu)子結(jié)構(gòu)的問題。

• 如果一個(gè)問題的全局最優(yōu)解可以通過組合局部子問題的最優(yōu)解求出，那么這個(gè)問題就具有最優(yōu)子結(jié)構(gòu)。我們已經(jīng)見過一些這樣的問題，比如歸并排序。歸并排序?qū)σ粋€(gè)列表進(jìn)行排序的方式就是先對(duì)子列表進(jìn)行排序，然后再合并子列表的排序結(jié)果。
• 如果求出一個(gè)問題的最優(yōu)解時(shí)需要對(duì)同樣的某個(gè)問題求解多次，那么這個(gè)問題就具有重疊子
  問題。

0/1背包問題具有這兩個(gè)特性，盡管不太明顯。我們要先看一個(gè)更明顯具有最優(yōu)子結(jié)構(gòu)和重疊子問題的問題。

又見斐波那契數(shù)列

之前我們介紹了一個(gè)很直觀的斐波那契數(shù)列的遞歸實(shí)現(xiàn)：

def fib(n):
"""假設(shè)n是非負(fù)整數(shù)
返回第n個(gè)斐波那契數(shù)"""
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

雖然這個(gè)遞歸實(shí)現(xiàn)是正確的，但效率太差。復(fù)雜度的增長與函數(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ù)上。舉個(gè)例子，我們看一下fib(6)的調(diào)用樹：

遞歸形式的斐波那契調(diào)用樹

請(qǐng)注意，我們?cè)谝槐橛忠槐榈赜?jì)算同一個(gè)值。例如，fib(3)被調(diào)用了3次，而且每一次調(diào)用又引發(fā)了對(duì)fib函數(shù)的另外4次調(diào)用。很容易就能想到，可以將fib函數(shù)的第一次調(diào)用結(jié)果保存下來，然后在需要的時(shí)候直接查找，而不是重新計(jì)算。這種方法稱為備忘錄法，是動(dòng)態(tài)規(guī)劃的核心思想。

下面給出了一個(gè)基于備忘錄法的斐波那契函數(shù)的具體實(shí)現(xiàn)。函數(shù)fastFib中有一個(gè)參數(shù)memo，用來記錄已經(jīng)計(jì)算過的函數(shù)值，這個(gè)參數(shù)的默認(rèn)值是一個(gè)空字典。當(dāng)使用一個(gè)大于1的整數(shù)n調(diào)用fastFib時(shí)，fastFib會(huì)先在memo中尋找n，如果沒有找到（因?yàn)檫@時(shí)是第一次使用這個(gè)值調(diào)用fastFib），就會(huì)拋出一個(gè)異常。此時(shí)，fastFib就使用標(biāo)準(zhǔn)的斐波那契遞推公式，并將結(jié)果保存在memo中。

def fastFib(n, memo = {}):
    """假設(shè)n是非負(fù)整數(shù)，memo只進(jìn)行遞歸調(diào)用 返回第n個(gè)斐波那契數(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

動(dòng)態(tài)規(guī)劃與0/1 背包問題

我們介紹過一種最優(yōu)化問題，即0/1背包問題?；貞浺幌拢覀兘榻B了一種復(fù)雜度為O(nlog(n))的貪婪算法，但這種算法不能保證找到最優(yōu)解。除此之外，我們還介紹了一種可以保證找到最優(yōu)解的暴力算法，但運(yùn)行時(shí)間是指數(shù)增長的。動(dòng)態(tài)規(guī)劃可以提供一種實(shí)用的方法，在合理的時(shí)間內(nèi)解決大部分0/1背包問題。作為推導(dǎo)解決方案的第一步，我們先基于窮舉法得到一個(gè)指數(shù)級(jí)別的解法。核心思想就是構(gòu)造一個(gè)根二叉樹，枚舉所有滿足重量約束的狀態(tài)，從而探索可行解空間。

在0/1背包問題的搜索樹中，每個(gè)節(jié)點(diǎn)都使用一個(gè)四元組進(jìn)行標(biāo)注，這個(gè)四元組表示的是這種背包問題的一個(gè)局部解。四元組中的四個(gè)元素如下：

• 要帶走的物品集合；
• 還沒有決定是否要帶走的物品列表；
• 要帶走的物品集合中的物品總價(jià)值（這個(gè)值只是為了優(yōu)化算法，因?yàn)榭梢詮募现杏?jì)算出這個(gè)值）；
• 背包的剩余空間（這也同樣是一種算法優(yōu)化方式，因?yàn)檫@個(gè)值可以通過背包允許的總重量減去當(dāng)前要帶走的物品總重量計(jì)算出來）。

這個(gè)樹是從根節(jié)點(diǎn)開始，自頂向下地構(gòu)建出來的。我們從待定物品中選擇出一個(gè)，如果背包放得下這個(gè)物品，就建立一個(gè)節(jié)點(diǎn)，反映出選擇帶走這個(gè)物品的后果。按照慣例，我們將這個(gè)節(jié)點(diǎn)作為左子節(jié)點(diǎn)，而用右子節(jié)點(diǎn)表示不帶走這個(gè)物品的后果。以遞歸方式不斷執(zhí)行這個(gè)過程，直到背包被裝滿或者沒有待定物品。因?yàn)槊織l邊都表示一個(gè)決策（帶走或不帶走某個(gè)物品），所以這種樹稱為決策樹。

如下是一個(gè)表示物品集合的表格。

給出一個(gè)決策樹，在背包能夠容納的最大重量為5的假設(shè)之下，可以確定應(yīng)該帶走哪些物品。樹的根節(jié)點(diǎn)（節(jié)點(diǎn)0）有一個(gè)標(biāo)簽<{}, [a, b, c, d], 0, 5>，表示沒有選擇物品，所有物品都處于待定狀態(tài)，帶走的物品總值為0，背包剩余空間還能容納的重量為5。節(jié)點(diǎn)1表示物品a被帶走，物品[b, c, d]處于待定狀態(tài)，帶走的物品總值為6，背包還能容納2的重量。節(jié)點(diǎn)1沒有左子節(jié)點(diǎn)，因?yàn)槲锲穊的重量為3，不能放在背包中。

背包問題的決策樹

對(duì)于每個(gè)葉節(jié)點(diǎn)，或者第二個(gè)元素為空列表（表示沒有物品可以考慮是否帶走），或者第四個(gè)元素為0（表示背包中已經(jīng)沒有剩余空間）。這種深度優(yōu)先的樹搜索使用遞歸實(shí)現(xiàn)如下。

def maxVal(toConsider, avail):
"""假設(shè)toConsider是一個(gè)物品列表，avail表示重量
返回一個(gè)元組表示0/1背包問題的解，包括物品總價(jià)值和物品列表"""
    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

程序中是否還有重疊子問題呢？乍一看似乎沒有。在樹的每一層，我們考慮的都是不同的可用物品集合，這說明如果確實(shí)存在普通的重疊子問題，那么它們一定在樹的同一層。實(shí)際上，同一層的每個(gè)節(jié)點(diǎn)的待定物品集合確實(shí)是一樣的。不過，從圖13-4中的標(biāo)注可以看出，某層的每一個(gè)節(jié)點(diǎn)的待定物品集合和更高層中節(jié)點(diǎn)的待定物品集合是不同的。

考慮一下每個(gè)節(jié)點(diǎn)需要解決的問題。這個(gè)的問題就是，在給定剩余可用重量的情況下，從待定物品集中找到一個(gè)最優(yōu)的物品。決定剩余可用重量的不是帶走的具體物品或帶走的物品的總價(jià)值，而是帶走的物品的總重量。所以，舉例來說，在決策樹圖中，節(jié)點(diǎn)2和節(jié)點(diǎn)7要解決的實(shí)際上是同一個(gè)問題：在給定剩余可用重量為2的情況下，確定待定物品集合[c, d]中應(yīng)該帶走哪個(gè)物品。

下面的代碼利用最優(yōu)子結(jié)構(gòu)和重疊子問題，為0/1背包問題提供了一個(gè)動(dòng)態(tài)規(guī)劃解決方案。通過添加一個(gè)附加參數(shù)memo，記錄已經(jīng)解決的子問題的解。memo是使用字典實(shí)現(xiàn)的，它的鍵由toConsider的長度和剩余可用重量構(gòu)成。表達(dá)式len(toConsider)是待定物品集合的一種簡潔表示，可以這樣表示的原因是物品總是從列表toConsider的同一端（前端）被移除。

def fastMaxVal(toConsider, avail, memo = {}):
    """假設(shè)toConsider是物品列表，avail表示重量memo進(jìn)行遞歸調(diào)用
    返回一個(gè)元組表示0/1背包問題的解，包括物品總價(jià)值和物品列表"""
    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