問題描述

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

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

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

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

    現在我們經過前面的推理已經得到了一個基本的遞推關系，就是一個最優解的子解集也是最優的?？墒牵覀冊撛趺磥砬蟮眠@個最優解呢？我們這樣來看。假定我們定義一個函數c[i, w]表示到第i個元素為止，在限制總重量為w的情況下我們所能選擇到的最優解。那么這個最優解要么包含有i這個物品，要么不包含，肯定是這兩種情況中的一種。如果我們選擇了第i個物品，那么實際上這個最優解是c[i - 1, w-wi] + vi。而如果我們沒有選擇第i個物品，這個最優解是c[i-1, w]。這樣，實際上對于到底要不要取第i個物品，我們只要比較這兩種情況，哪個的結果值更大不就是最優的么？

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

    另外，對于初始的情況呢？很明顯c[0, w]里不管w是多少，肯定為0。因為它表示我們一個物品都不選擇的情況。c[i, 0]也一樣，當我們總重量限制為0時，肯定價值為0。

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

    有了這個關系，我們可以更進一步的來考慮代碼實現了。我們有這么一個遞歸的關系，其中，后面的函數結果其實是依賴于前面的結果的。我們只要按照前面求出來最基礎的最優條件，然后往后面一步步遞推，就可以找到結果了。

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