0-1背包問題（動态規劃）

關于01背包問題的優化

一、01背包問題介紹

背包問題是經典的動态規劃問題之一；

常見的01背包問題就是說有一堆物品，現在要裝入一個容器中，這些物品的重量和價值各不一緻，而容器的重量又是有限的，沒種物品隻能裝1個或者不裝（0個），求當重量限定為w時，這些物品能裝進去組合成的最高價值是多少？

分析：我們首先将物品排成一排（随機），依次标記為1号，2号。。。。然後從一号開始依次往裡放，放的時候判斷目前物品是不是應該放進去：

如果目前物品放進去之後的最高總價值 比 不放進去的最高總價值 大 ，那麼就是要放入，然後總價值取放入之後的

反之不放入，總價值依然取之前的值。

并且，在對同一個物品判斷時，從0依次增加容器的容量，直到上限w

目前物品放進去之後的最高總價值 = 上一号物品判斷時（容量 = 目前容量 - 目前物品重量 時）總價值 + 目前物品的價值

不放進去的最高總價值 = 上一号物品判斷的時候（容量 = 目前容量 時）總價值

是以有僞代碼如下：

if (目前物品重量 > 目前容量) {
        此時最高總價值 = 目前物品不放進去的最高總價值;  // 此時物品重量比容量大，放不進去，隻能取放不進去的情況
    } else {
        此時最高總價值 = max(目前物品不放進去的最高總價值, 目前物品放進去的最高總價值);
    }
           

是以，我們可以用一個狀态表來對整個過程進行描述。

假設現在是有三個物品 （不是三種）一号、二号、三号，重量分别為3，2，5； 價值分别為7,4,8; 目前容器容量為8，求最大價值。

首先，第一行，為沒有任何物品的時候，全部置0；

第二行，判斷一号物品能不能放：

當容量擴充為3的時候，一号物品終于能放，價值為7，由于目前也隻有一号，是以後面都是7；

第三行，判斷二号物品能不能放：

當容量擴充為2的時候，二号物品終于能放，價值為4，與不放進去的最高價值（一号物品在此容量時的值：0）進行比較，是以成功放進去；

當容量擴充為3的時候，二号物品一定放時，價值為4，與不放進去的最高價值（一号物品在此容量時的值：7）進行比較，決定不放進去了；

。。。

當容量擴充為5的時候，二号物品一定放時，最高價值為（一号物品在（目前容量 - 二号物品的重量）時的價值+二号物品的價值）

=（一号物品在容量為（5-2）的時候 + 二号物品的價值）= 7 + 4 =11

。。。【如下表】

容量 0 1 2 3 4 5 6 7 8

無 0 0 0 0 0 0 0 0 0

一号 0 0 0 7 7 7 7 7 7

二号 0 0 4 7 7 11 11 11 11

三号 0 0 4 7 7 11 11 12 15

是以有代碼如下：

public static int getMaxValue(int[] weight, int[] value, int w) {
    int n = weight.length;
    int[][] table = new int[n + 1][w + 1];
    for (int i = 1; i <= n; i++) {     // 物品周遊（第0行肯定全是0，是以不用周遊）
        for (int j = 0; j <= w; j++) { // 背包大小遞增
            if (weight[i-1] > j) {     // 目前物品i的重量比背包容量j大，裝不下，隻能是不裝
                table[i][j] = table[i - 1][j];
            } else {                   // 裝得下，Max{不裝物品i， 裝物品i}
                table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weight[i-1]] + value[i-1]);
            }
        }
    }
    return table[n][w];
}
           

提問：為什麼要【n+1】行？

——因為之後每一個數都需要與上一行做比較，一号物品放入的時候也需要與沒放入的時候做比較，是以空出一行作為“沒有物品的時候”；

為什麼要【w+1】列？

——因為在容量遞增時，第一個物品能放的時候，需要與容量減去目前物品的重量，也就是容量為0的時候做比較，是以，也是需要一列作為“0容量的時候”；

為什麼是weight[i - 1] 和 value[i - 1]？

——因為傳入的重量和價值必然是從一号物品開始，而我們的表是從“沒有物品”和“0容量”開始，多了一行和一列，是以 i 是目前物品的标号，而目前物品下标為【标号-1】；
           

二、空間複雜度優化

很顯然，上面算法的空間複雜度為矩陣大小【n+1】*【w+1】。

n可能不大，但是實際應用傷的w可能會很大，這樣造成了比較大的空間占用。

而仔細觀察發現，矩陣中的值隻與目前值的左上角的矩陣裡的值有關，如圖二号物品容量為4時的價值7，隻與綠色标注值有關。

容量 0 1 2 3 4 5 6 7 8

無 0 0 0 0 0 0 0 0 0

一号 0 0 0 7 7 7 7 7 7

二号 0 0 4 7 7 11 11 11 11

三号 0 0 4 7 7 11 11 12 15

　　并且我們是按行進行更新的，是以我們用一個一維資料就能進行狀态的更替，不過要注意更新的方向。

是以依賴關系為：下面依賴上面，右邊依賴左邊；

如果正常地從左到右邊，那麼右邊面等待更新的值需要的依賴（左邊）就會被覆寫掉，是以應該每行從右邊開始更新。代碼如下：

public static int getMaxValueByOne(int[] weight, int[] value, int w) {
    int n = weight.length;
    int[] table = new int[w + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = w; j >= 0; j--) {
            if (weight[i-1] <= j) {
                table[j] = Math.max(table[j], table[j - weight[i-1]] + value[i-1]);
            }
        }
    }
    return table[w];
}
           

如此一來，01背包的空間複雜度就降為了O（w）。

清風吹斜陽（轉載http://www.cnblogs.com/Xieyang-blog/p/9432711.html）

——唯有更努力才能讓一切都是最好的安排。