【動態規劃】絕X不翻車的01背包問題(詳)

領扣鏈接

題目：
有 n 個物品和一個大小為 m 的背包. 給定陣列 A 表示每個物品的大小和陣列 V 表示每個物品的價值，問最多能裝入背包的總價值是多大?

注：

1. A[i], V[i], n, m 均為整數
2. 你不能將物品進行切分
3. 你所挑選的要裝入背包的物品的總大小不能超過 m
4. 每個物品只能取一次
5. m <= 1000并且len(A),len(V)<=100

思路分析：

拿到這道題目時，以一般人的思維考慮，想要使得背包中的總價值最大，就需要同時考慮n個物品的體積和價值，經過一番抉擇后，得到最優組合解，

這n件物品每一件都有放入或者不放入的可能性，

首先就需要考慮背包的體積和即將要放入的物品之間的大小關系，

1. 某物品肥的要死，整的比背包還大，那么該物品就不存在被放入的可能性，丟了~
2. 某物品的體積比背包小，那么就需要考慮是將它放入背包所產生的價值大還是不放入產生的價值大，選擇這兩選擇中價值更大的，

將上面的思路進行轉換成動態規劃的四個角度就應該是：

1. 狀態定義F(i，j)：前i個物品放進大小為j的背包中所獲得的最大的價值量，

   例如F（4，8）就代表著背包大小為8時考慮前4個物品放入的情況，使得背包中價值最大的最佳組合產生的價值量

2. 狀態間的轉移方程定義F（i，j）：

• 當A[i-1] > j時，F（i，j）= F（i-1，j）；代表著第i個物品的體積比背包還大，將之丟棄，此時背包的價值量和將前i-1個物品放進大小為j的背包所產生的最大價值量是一樣的，

• 當A[i-1] <= j時，F（i，j）= Max（F（i-1，j），F（i-1，j-A[i-1]）+V[i-1]）；

  代表著第i個物品的體積比背包小，那么就存在放不放入背包的選擇，F（i，j）的值將是這兩種選擇中能產生最大價值的那一選擇，

  倘使不放入背包，那么此時背包的價值量和將前i-1個物品放進大小為j的背包所產生的最大價值量是一樣的；

  倘使放進背包，那么就需要在已經對前i-1個物品進行最佳選擇的背包中騰出第i個物品的體積（A[i-1]），這塊兒體積就是用來迎接物品i的到來的，然后在加上第i個物品的價值（V[i-1]），

3. 狀態的初始化 F（0，j）= F（i，0）= 0；當沒有放任何物品時或者背包的大小為0時，背包的價值都為0

4. 回傳結果F（n，m）即將n個物品放入大小為m背包產生的最大價值量

舉例分析：

這里有4個物品，背包的大小為8，物品大小陣列A[4]={3,5,1,4}; 物品價值陣列V[4]={1,3,2,3};

為了更加形象的說明該問題，采取列二維表的方式來驗證我們之前的分析思路：

橫坐標為背包的容量（j），縱坐標為物品的編號（i），每個坐標就代表著前i個物品放進大小為j的背包中所獲得的最大的價值量，

當沒有物品或者背包的容量為0時，背包中的價值為0，此乃狀態初始化，

當決定放1號是否放進背包時：

• 背包容量小于3（1號物品大小）時，1號物品可以沒有放下的可能，棄之~此時背包價值量為0

• 背包容量大于等于3時

  • F（1，3） = max(F（0，3），F（0，3-3）+ V[0]) = F（0，0）+ 1= 1

  • F（1，4）= max(F（0，4），F（0，4-3）+ V[0]) = F（0，1）+ 1 = 1

    …

  • F（1，8） = max(F（0，8），F（0，8-3）+ V[0]) = F（0，5）+ 1= 1

當決定放2號是否放進背包時：

• 背包容量小于5（2號物品大小）時，2號物品可以沒有放下的可能，棄之~，此時背包價值量和F（1，j）時相同（1<=j<=4）
• 背包容量大于等于5時
  • F（2，5） = max(F（1，5），F（1，5-5）+ V[1]) = F（1，0）+ 3= 3
  • F（2，6） = max(F（1，6），F（1，6-5）+ V[1]) = F（1，1）+ 3= 3
  • F（2，7） = max(F（1，7），F（1，7-5）+ V[1]) = F（1，2）+ 3= 3
  • F（2，8） = max(F（1，8），F（1，8-5）+ V[1]) = F（1，3）+ 3= 4

當決定放3號是否放進背包時：

• 背包容量小于1（3號物品大小）時，3號物品可以沒有放下的可能，棄之~，此時背包價值量為0

• 背包容量大于等于1時

  • F（3，1） = max(F（2，1），F（2，1-1）+ V[2]) = F（2，0）+ 2= 2

  • F（3，2） = max(F（2，2），F（2，2-1）+ V[2]) = F（2，1）+ 2= 2

    …

  • F（3，8） = max(F（2，8），F（2，8-1）+ V[2]) = F（2，7）+ 2= 5

當決定放4號是否放進背包時：

• 背包容量小于4（4號物品大小）時，4號物品可以沒有放下的可能，棄之~，此時背包價值量和F（3，j）時相同（1<=j<=3）

• 背包容量大于等于4時

  • F（4，4） = max(F（3，4），F（3，4-4）+ V[3]) = F（3，4）= 4

  • F（4，5） = max(F（3，5），F（3，5-4）+ V[3]) = F（3，1）+ 3= 5

    …

  • F（4，8） = max(F（3，8），F（3，8-4）+ V[3]) = F（3，4）+ 3= 6

回溯歸納：

從表中的右下角開始回溯，當前i個物品產生的最大價值量和前i-1個物品產生的最大價值量相等，說明第i個物品沒有被放入背包，反之，被放入背包，

在本例子中

F（4，8）!= F（3，8）說明物品4放進背包中，物品4的大小為4，說明背包中剩余4容量放其他物品

F（3，4）!= F（2，4）說明物品3放進背包中，物品3的大小為1，說明背包中剩余3容量放其他物品

F（2，3）== F（1，3）說明物品2沒放進背包中，背包中剩余3容量放其他物品

F（1，3）!= F（0，3）說明物品1放進背包中，物品1的大小為3，背包容量為0

總結：物品1、物品3、物品4被放進背包中

代碼實作

public class Solution {
    public int backPackII(int m, int[] A, int[] V) {
        int n = A.length;//物品的數量
        if(n == 0 && m == 0) return 0;//若沒有物品或背包容量為0，就直接回傳0，背包價值為0
        int[][] maxV = new int[n+1][m+1];//創建二維陣列來存放價值狀態
        //狀態初始化
        //在Java中陣列被初始化大小后，每個元素的大小默認為0，因此maxV[i][0]和maxV[0][j]不再初始化也是可以的
        for(int i = 0;i <= n;i ++) {
            maxV[i][0] = 0;
        }
        for(int j = 0;j <= m;j ++) {
            maxV[0][j] = 0;
        }
        //狀態轉移
        for(int i = 1;i <= n;i ++) {
            for(int j = 1;j <= m;j ++) {
                if(A[i-1] <= j) {
                    maxV[i][j] = Math.max(maxV[i-1][j],maxV[i-1][j-A[i-1]]+V[i-1]);//背包容量大于物品i的情況
                }else{
                    maxV[i][j] = maxV[i-1][j];//背包容量小于物品i的情況
                }
            }
        }
        return maxV[n][m];//回傳結果
    }
}

代碼升級

事實上，動態規劃問題中的狀態轉移是指轉移一步的所獲得的狀態，在本題中，也就是說第i個物品放入情況所獲得的背包最大價值只會和第i-1個物品放入情況所獲得的背包最大價值有關，比那更之前的物品放不放，背包價值如何根本就不需要關心，因為動態規劃問題講究的就是記錄每個小問題的狀態，然后一步步推導大問題的程序，

既然如此，我們可以干脆就建立一個大小為m（背包最大容量）一維陣列來存放第i-1個物品放入與否后背包的價值得了，第i個物品放入與否后背包的價值直接在那一維陣列中改動，

思想和上面是一樣的，不同的是陣列變成了一維的，而且在第二層遍歷的時候要從后向前遍歷，如果從前向后遍歷的話，就會出現后面的狀態想要用到前面的狀態的值時，前面狀態值早就被篡改了，所得到的結果自然會出錯，

關于從后向前遍歷這一點可以舉個簡單的例子：

array[5] = {1,2,3,4,5};

現在想讓array[0]不變，陣列中其他元素都變成其前面一個元素的2倍，即array[i] = array[i-1]*2 (0<i<5)

方法一：重新創建一個陣列a[]來存放結果，那么遍歷array時從前往后還是從后往前都無所謂，array陣列沒有被篡改，結果都一樣正確

方法二：為節省空間，干脆直接在array陣列上直接改得了，如果從前向后，array[0]= 1,array[1]=2,array[2]= 4,array[3]= 8 !?出現BUG了，不應該是6蠻，原因就在于后面的結果會用到array陣列前面的值，從前向后遍歷就會篡改array陣列前面的值，從后向前就不會出現這樣的狀況，

方法一就相當于本案例中創建二維陣列的情況，方法二就相當于本案例中創建一維陣列的情況，因此需要注意遍歷方向問題，至關重要！

public class Solution {
    public int backPackII(int m, int[] A, int[] V) {
        int n = A.length;//物品的數量
        if(n == 0 && m == 0) return 0;//若沒有物品或背包容量為0，就直接回傳0，背包價值為0
        int[] maxV = new int[m+1];//創建一維陣列來存放價值狀態
        for(int j = 0;j <= m;j ++) {
            maxV[j] = 0;
        }
        for(int i = 1;i <= n;i ++) {
            for(int j = m;j >=0;j --) {
                if(A[i-1] <= j) {
                    maxV[j] = Math.max(maxV[j],maxV[j-A[i-1]]+V[i-1]);
                }
            }
        }
        return maxV[m];
    }
}

完！