分治法

當(dāng)我們要處理一個(gè)復(fù)雜的問題時(shí)，如果直接求解難度很大，那我們可以采用分治法漩仙，將大問題拆分成可以解決的小問題缆镣。分治法的過程有三步：

• 分解：將大問題劃分成多個(gè)子問題芽突，子問題的形式與原問題一樣，只是規(guī)模變小了董瞻；
• 求值：遞歸的將子問題劃分成更小的子問題寞蚌，直到子問題可以直接求解；
• 合并：將子問題的解組合成原問題的解

分治法或者叫分治思想钠糊，是算法中一個(gè)很重要的思想挟秤。使用到分治法的案例很多，比較常見的如歸并排序抄伍、快速排序艘刚、斐波那契數(shù)列等等。

我們發(fā)現(xiàn)分治法能夠讓我們更容易理解和處理復(fù)雜問題截珍，但是簡單的分治法有一個(gè)缺陷攀甚，可能存在同一個(gè)子問題被重復(fù)計(jì)算的情況，比如背包問題岗喉。此時(shí)我們可以使用動(dòng)態(tài)規(guī)劃來解決秋度。

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃與分治法相似，都是通過組合子問題的解來求解原問題钱床。不同的是荚斯，動(dòng)態(tài)規(guī)劃將相同的子問題的解保存起來，保證相同的子問題不會(huì)被重復(fù)計(jì)算诞丽。
動(dòng)態(tài)規(guī)劃解決的問題應(yīng)該具有兩個(gè)要素：

• 最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解包含子問題的最優(yōu)解
• 子問題重疊：相同的子問題的值需要保存起來

動(dòng)態(tài)規(guī)劃步驟：

• 刻畫一個(gè)最優(yōu)解的結(jié)構(gòu)特征
• 遞歸定義最優(yōu)解的值
• 計(jì)算最優(yōu)解的值鲸拥，通常采用自底向上的方法（因?yàn)樽缘紫蛏媳苊饬祟l繁的調(diào)用遞歸函數(shù)帶來的開銷）
• 利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解

前三步是求得一個(gè)最優(yōu)解，而第四步則是在步驟三中維護(hù)一個(gè)額外的信息僧免，以便用來構(gòu)造一個(gè)最優(yōu)解刑赶。

01背包

結(jié)合背包問題來理解動(dòng)態(tài)規(guī)劃：
有n個(gè)物品和一個(gè)承重為m的背包. 給定數(shù)組W表示每個(gè)物品的重量和數(shù)組V表示每個(gè)物品的價(jià)值。問最多能裝入背包的總價(jià)值是多大?
如果每個(gè)物品只有裝和不裝兩種狀態(tài)懂衩，那么稱為01背包問題撞叨。
例如：len = 5, all_weight = 10, item_weights = [2, 2, 6, 5, 4], item_values = [6, 3, 5, 4, 6]

最優(yōu)解的結(jié)構(gòu)特征：
動(dòng)態(tài)規(guī)劃方法的第一步是尋找最優(yōu)子結(jié)構(gòu)金踪，然后就可以利用這種子結(jié)構(gòu)從子問題的最優(yōu)解構(gòu)造出原問題的最優(yōu)解。
假設(shè)(x1牵敷，x2胡岔，…，xn)是01背包問題的最優(yōu)解枷餐，則有(x2靶瘸，x3，…毛肋，xn)是其子問題的最優(yōu)解怨咪，假設(shè)(y2，y3润匙，…诗眨，yn)是上述問題的子問題最優(yōu)解，則有(v_y2+v_y3+…+v_yn)+v_x1 > (v_x2+v_x3+…+v_xn)+v_x1孕讳。說明(x1匠楚，y2，y3厂财，…芋簿，yn)才是該01背包問題的最優(yōu)解，這與最開始的假設(shè)(x1蟀苛，x2益咬，…，xn)是01背包問題的最優(yōu)解相矛盾帜平，故01背包問題具有最優(yōu)解的結(jié)構(gòu)特征。

遞歸定義最優(yōu)解的值：
前i個(gè)物體放入容量為j的最大價(jià)值為values[i][j]梅鹦，對(duì)于第i個(gè)物品裆甩，我們只有放和不放兩種情況，values[i][j]的值應(yīng)該是兩種情況的較大值齐唆。那么就可以表示為：
values[i][j] = max(values[i - 1][j], values[i - 1][j - item_weights[i - 1]] + item_values[i - 1])
所以values[i][j]問題就拆分成立了max(values[i - 1][j]和values[i - 1][j - item_weights[i - 1]] + item_values[i - 1]兩個(gè)子問題嗤栓。

• values[i][j] = 0 （如果 i == 0 or j == 0）
• values[i][j] = max(values[i - 1][j], values[i - 1][j - item_weights[i - 1]] + item_values[i - 1])

計(jì)算最優(yōu)解的值&利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解
我們采用自底向上的方案，所以需要兩個(gè)for循環(huán)箍邮，遍歷len和all_weight茉帅，同時(shí)使用雙重?cái)?shù)組values來保存values[i][j]的值，由于Python實(shí)現(xiàn)更加方便锭弊，所以示例代碼我使用了Python2堪澎。
需要注意的是，在計(jì)算哪些物品被選擇時(shí)味滞，就是對(duì)前面選擇物品邏輯的一個(gè)逆向推導(dǎo)樱蛤。

import itertools
def knapsack_01_v1(all_weight, item_weights, item_values, len):
    values = [[0] * (all_weight + 1) for x in xrange(len + 1)]
    for i in xrange(1, len + 1):
        item_weight = item_weights[i - 1]
        item_value = item_values[i - 1]
        for j in xrange(1, all_weight + 1):
            if j >= item_weight:
                values[i][j] = max(values[i - 1][j], values[i - 1][j - item_weight] + item_value)
            else:
                values[i][j] = values[i - 1][j]
    print 'max value: ', max(itertools.chain(*values))
    
    print 'select:'
    w = all_weight
    for i in xrange(len, 0, -1):
        if values[i][w] != values[i - 1][w]:
            print (item_values[i - 1], item_weights[i - 1])
            w -= item_weights[i - 1]

all_weight = 10
item_weights = [2, 2, 6, 5, 4]
item_values = [6, 3,  5, 4, 6]
knapsack_01_v1(all_weight, item_weights, item_values, len(item_weights))

結(jié)果：

max value:  15
select:
(6, 4)
(3, 2)
(6, 2)

時(shí)間復(fù)雜度和空間復(fù)雜度都是O(n*m)钮呀，如果我們只需要求得最優(yōu)解，而不用關(guān)心選擇哪些物品昨凡，我們可以對(duì)空間進(jìn)行優(yōu)化：二維數(shù)組values[len][all_weight]轉(zhuǎn)一維數(shù)組values[all_weight]爽醋。
values[j]表示values[i][j]，根據(jù)遞推定義便脊，我們?cè)趺丛撛趺传@得values[i - 1][j]和values[i - 1][j - item_weights[i - 1]]呢蚂四？
答案是如果我們對(duì)all_weight進(jìn)行逆遍歷，這樣此時(shí)一維的values[j]代表的就是二維的values[i - 1][j]哪痰，一維的values[j - item_weights[i - 1]]代表的就是二維的values[i - 1][j - item_weights[i - 1]]遂赠。
由于保存的信息被覆蓋，所以沒法求得選了哪些物品妒御。

def knapsack_01_v2(all_weight, item_weights, item_values, len):
    values = [0] * (all_weight + 1)
    for i in xrange(1, len + 1):
        item_weight = item_weights[i - 1]
        item_value = item_values[i - 1]
        for j in xrange(all_weight, item_weight - 1, -1):
            values[j] = max(values[j], values[j - item_weight] + item_value)

    print 'max value: ', max(values)

完全背包

01背包的物品只能選或者不選解愤，如果物品可以選擇無限個(gè)就是完全背包。
理解了01背包乎莉，再來理解完全背包就容易多了送讲，唯一區(qū)別就是物品可以是多個(gè)，所以某個(gè)物品的狀態(tài)從裝和不裝轉(zhuǎn)變?yōu)檠b0~k（k = j / item_weight）個(gè)惋啃。

遞歸定義最優(yōu)解的值：

• values[i][j] = 0 （如果 i == 0 or j == 0）
• values[i][j] = max(map(lambda x: values[i - 1][j - item_weight * x] + item_value * x, xrange(k+1)))

def knapsack_v1(all_weight, item_weights, item_values, len):
    values = [[0] * (all_weight + 1) for _ in xrange(len + 1)]
    for i in xrange(1, len + 1):
        item_weight = item_weights[i - 1]
        item_value = item_values[i - 1]
        for j in xrange(1, all_weight + 1):
            if j >= item_weight:
                k = j / item_weight
                values[i][j] = max(map(lambda x: values[i - 1][j - item_weight * x] + item_value * x, xrange(k+1)))
            else:
                values[i][j] = values[i - 1][j]
    print 'max value: ', max(itertools.chain(*values))

如果x大于1哼鬓，那么values[i][j - item_weight]必然計(jì)算過j物品個(gè)數(shù)為1的情況，這意味著重復(fù)計(jì)算边灭，所以空間上我們可以做進(jìn)一步的優(yōu)化异希，可以少一層遍歷：

def knapsack_v2(all_weight, item_weights, item_values, len):
    values = [[0] * (all_weight + 1) for _ in xrange(len + 1)]
    for i in xrange(1, len + 1):
        item_weight = item_weights[i - 1]
        item_value = item_values[i - 1]
        for j in xrange(1, all_weight + 1):
            if j >= item_weight:
                values[i][j] = max(values[i - 1][j], values[i][j - item_weight] + item_value)
            else:
                values[i][j] = values[i - 1][j]
    print 'max value: ', max(itertools.chain(*values))

和01背包一樣，我們可以進(jìn)一步把二維數(shù)組優(yōu)化成一維數(shù)組绒瘦，和01背包不一樣的是称簿，完全背包的內(nèi)循環(huán)是升序，原因是計(jì)算某個(gè)物品有x個(gè)的情況需要先計(jì)算這個(gè)物品有x-1個(gè)的結(jié)果惰帽。

def knapsack_v3(all_weight, item_weights, item_values, len):
    values = [0] * (all_weight + 1)
    for i in xrange(1, len + 1):
        item_weight = item_weights[i - 1]
        item_value = item_values[i - 1]
        for j in xrange(item_weight, all_weight + 1):
            values[j] = max(values[j], values[j - item_weight] + item_value)

    print 'max value: ', max(values)

多重背包

多重背包是指物品的選擇有個(gè)數(shù)限制憨降，比如說item_counts = [2, 3, 3, 3, 3]。
多重背包可以在knapsack_v1算法中做個(gè)微調(diào)该酗，限制每個(gè)物品數(shù)量授药。

由于每組物品的件數(shù)均不一樣，所以不能使用完全背包的優(yōu)化方法（具體件數(shù)不可控）呜魄，因此采用另一種思路——二進(jìn)制優(yōu)化悔叽。
將每一種物品由1.2.4.8.16.128...的件數(shù)打包，不足一組的零頭重新打包爵嗅，轉(zhuǎn)化為01背包問題娇澎。

混合背包

現(xiàn)在我們來考慮一種更為復(fù)雜的情況，如果可選的物品同時(shí)具有上述三種特性操骡，即：有的物品只能選一個(gè)九火，有的物品可以選擇任意多個(gè)赚窃，有的物品只能選擇有限多個(gè)，那么此時(shí)該如何決策呢岔激？

其實(shí)有了上面的總結(jié)和抽象勒极，這種混合背包問題就小菜一碟了。

回顧一下上面的三種背包問題的抽象解虑鼎，就會(huì)發(fā)現(xiàn)他們每次都只會(huì)考慮一種物品辱匿，區(qū)別只在于第i個(gè)物品的可選策略。所以對(duì)于混合背包問題炫彩，同樣也可以一個(gè)一個(gè)物品考慮匾七，如果這個(gè)物品是最多選一個(gè)，那么就采用01背包的解決策略江兢，如果是可以選擇任意多個(gè)昨忆，那么就使用完全背包的解決策略，如果只能選擇有限多個(gè)杉允，那么就使用多重背包的解決策略邑贴。

分組背包

01背包的變種，每組物品有若干個(gè)叔磷，同一組內(nèi)的物品最多只能選一個(gè)拢驾，把某個(gè)物品升級(jí)成某組物品。
和01背包幾乎一樣改基，多一層循環(huán)繁疤，遍歷一個(gè)組的物品，判斷選或者不選秕狰。

二維費(fèi)用的背包

包既有重量限制稠腊，又有體積限制，加一個(gè)for循環(huán)判斷體積即可

動(dòng)態(tài)規(guī)劃應(yīng)用

在《算法導(dǎo)論》一書中還介紹了下面情景可以使用動(dòng)態(tài)規(guī)劃來處理

1. 鋼條切割
2. 矩陣鏈乘法
3. 最長公共子序列：序列A=[5, 3, 2, 5, 7, 1, 8, 9]和B=[1, 5, 8, 2, 6, 7, 9]的公共子序列是[5, 2, 7, 9]
4. 最優(yōu)二叉搜索樹

引用

《算法導(dǎo)論》
背包問題九講 2.0 beta1.2