問題描述

    假設(shè)我們有n件物品，分別編號為1, 2...n。其中編號為i的物品價(jià)值為vi，它的重量為wi。為了簡化問題，假定價(jià)值和重量都是整數(shù)值。現(xiàn)在，假設(shè)我們有一個(gè)背包，它能夠承載的重量是W。現(xiàn)在，我們希望往包里裝這些物品，使得包里裝的物品價(jià)值最大化，那么我們該如何來選擇裝的東西呢？問題結(jié)構(gòu)如下圖所示：

    這個(gè)問題其實(shí)根據(jù)不同的情況可以歸結(jié)為不同的解決方法。假定我們這里選取的物品每個(gè)都是獨(dú)立的，不能選取部分。也就是說我們要么選取某個(gè)物品，要么不能選取，不能只選取一個(gè)物品的一部分。這種情況，我們稱之為0-1背包問題。

    我們來看這個(gè)問題。我們需要選擇n個(gè)元素中的若干個(gè)來形成最優(yōu)解，假定為k個(gè)。那么對于這k個(gè)元素a1, a2, ...ak來說，它們組成的物品組合必然滿足總重量<=背包重量限制，而且它們的價(jià)值必然是最大的。因?yàn)樗鼈兪俏覀兗俣ǖ淖顑?yōu)選擇嘛，肯定價(jià)值應(yīng)該是最大的。假定ak是我們按照前面順序放入的最后一個(gè)物品。它的重量為wk，它的價(jià)值為vk。既然我們前面選擇的這k個(gè)元素構(gòu)成了最優(yōu)選擇，如果我們把這個(gè)ak物品拿走，對應(yīng)于k-1個(gè)物品來說，它們所涵蓋的重量范圍為0-(W-wk)。假定W為背包允許承重的量。假定最終的價(jià)值是V，剩下的物品所構(gòu)成的價(jià)值為V-vk。這剩下的k-1個(gè)元素是不是構(gòu)成了一個(gè)這種W-wk的最優(yōu)解呢？

    我們可以用反證法來推導(dǎo)。假定拿走ak這個(gè)物品后，剩下的這些物品沒有構(gòu)成W-wk重量范圍的最佳價(jià)值選擇。那么我們肯定有另外k-1個(gè)元素，他們在W-wk重量范圍內(nèi)構(gòu)成的價(jià)值更大。如果這樣的話，我們用這k-1個(gè)物品再加上第k個(gè)，他們構(gòu)成的最終W重量范圍內(nèi)的價(jià)值就是最優(yōu)的。這豈不是和我們前面假設(shè)的k個(gè)元素構(gòu)成最佳矛盾了嗎？所以我們可以肯定，在這k個(gè)元素里拿掉最后那個(gè)元素，前面剩下的元素依然構(gòu)成一個(gè)最佳解。

    現(xiàn)在我們經(jīng)過前面的推理已經(jīng)得到了一個(gè)基本的遞推關(guān)系，就是一個(gè)最優(yōu)解的子解集也是最優(yōu)的。可是，我們該怎么來求得這個(gè)最優(yōu)解呢？我們這樣來看。假定我們定義一個(gè)函數(shù)c[i, w]表示到第i個(gè)元素為止，在限制總重量為w的情況下我們所能選擇到的最優(yōu)解。那么這個(gè)最優(yōu)解要么包含有i這個(gè)物品，要么不包含，肯定是這兩種情況中的一種。如果我們選擇了第i個(gè)物品，那么實(shí)際上這個(gè)最優(yōu)解是c[i - 1, w-wi] + vi。而如果我們沒有選擇第i個(gè)物品，這個(gè)最優(yōu)解是c[i-1, w]。這樣，實(shí)際上對于到底要不要取第i個(gè)物品，我們只要比較這兩種情況，哪個(gè)的結(jié)果值更大不就是最優(yōu)的么？

    在前面討論的關(guān)系里，還有一個(gè)情況我們需要考慮的就是，我們這個(gè)最優(yōu)解是基于選擇物品i時(shí)總重量還是在w范圍內(nèi)的，如果超出了呢？我們肯定不能選擇它，這就和c[i-1, w]一樣。

    另外，對于初始的情況呢？很明顯c[0, w]里不管w是多少，肯定為0。因?yàn)樗硎疚覀円粋€(gè)物品都不選擇的情況。c[i, 0]也一樣，當(dāng)我們總重量限制為0時(shí)，肯定價(jià)值為0。

    這樣，基于我們前面討論的這3個(gè)部分，我們可以得到一個(gè)如下的遞推公式：

    有了這個(gè)關(guān)系，我們可以更進(jìn)一步的來考慮代碼實(shí)現(xiàn)了。我們有這么一個(gè)遞歸的關(guān)系，其中，后面的函數(shù)結(jié)果其實(shí)是依賴于前面的結(jié)果的。我們只要按照前面求出來最基礎(chǔ)的最優(yōu)條件，然后往后面一步步遞推，就可以找到結(jié)果了。

#n個(gè)物體的重量(w[0]無用)w = [0, 2, 2, 6, 5, 4]#n個(gè)物體的價(jià)值(p[0]無用)p = [0, 6, 3, 5, 4, 6]#計(jì)算n的個(gè)數(shù)n = len(w) - 1#背包的載重量m = 10#裝入背包的物體，元素為True時(shí)，對應(yīng)物體被裝入(x[0]無用)x = [False for raw in range(n + 1)]v = 0#optp[i][j]表示在前i個(gè)物體中，能夠裝入載重量為j的背包中的物體的最大價(jià)值optp = [[0 for col in range(m + 1)] for raw in range(n + 1)] def knapsack_dynamic(w, p, n, m, x):    #計(jì)算optp[i][j]    for i in range(1, n + 1):        for j in range(1, m + 1):            optp[i][j] = optp[i - 1][j]            if (j >= w[i]) and (optp[i - 1][j - w[i]] + p[i] > optp[i - 1][j]):                optp[i][j] = optp[i - 1][j - w[i]] + p[i]        #遞推裝入背包的物體    j = m    for i in range(n, 0, -1):        if optp[i][j] > optp[i - 1][j]:            x[i] = True            j = j - w[i]          #返回最大價(jià)值    v = optp[n][m]    return v 
    此題的核心就在d_k兩個(gè)循環(huán)體里，因?yàn)橹耙呀?jīng)實(shí)現(xiàn)了一個(gè)類二維數(shù)組，所有dp[ 0 ] [ j ] dp[ i ][ 0 ]都是零，所以從i=1開始，通過循環(huán)--遞歸一層一層的賦值，所有的下一層值都由上一層的值相等決定或者，dp i-1，j-w[ i ]+p[ i ]決定，最后全部鋪滿，在求最大值的時(shí)候，直接取表格中的值即可。 
    這個(gè)背包問題困擾了我兩天，才坎坎理解了它，在此很感謝下面兩篇文章的幫助，本篇文章除了最后的理解也都是引用了它們的文章（懶癌發(fā)作，是在是不愿意自己寫了......）
    ~本篇文章參考：
    1:http://blog.sina.com.cn/s/blog_3fe961ae0100zap7.html    2:http://shmilyaw-hotmail-com.VEvb.com/blog/2009761