動态規劃：0-1背包問題（遞歸和非遞歸java實作）——03

背包問題

• 0-1背包問題是動态規劃中的經典例題，和我上一篇寫的曠工挖礦的思路是一模一樣的

問題描述

• 有n個物品，它們有各自的體積和價值，現有給定容量的背包，如何讓背包裡裝入的物品具有最大的價值總和？

  

算法思路

• 往往動态規劃的題目從最後一步開始分析會有着不錯的結果，這裡假設背包容量為10
• 首先假設F（c，n）的意義是容量為 c 的背包裝前 n 個物品的最大價值，w【i】指第 i 個物品的體積，v【i】指第 i 個物品的價值
• 而我們所說的最後一步是哪一步呢？其實就是從F（10, 3）到F（10，4）的過程，求出容量為10的背包裝這四個物品的最大價值。那麼F（10,3）和F（10,4）又有什麼關系呢？
• 假設我們現在已經知道了F（10,3），也就是10的容量裝前三個物品的最大價值，那麼此時我們将第四個物品加入計算的話，無非就是兩種選擇：裝或者不裝這第四個物品
  • 如果不裝這第四個物品：那麼這種情況的最大價值為 M1 = F（10,3）
  • 如果裝這第四個物品：那麼就要将分出5的容量去裝，另外5的容量去裝前三個，是以此時的最大價值為 M2 = F（5,3）+ v【4】
  • 是以我們我們求出的F（10,4） = Max（M1，M2）

• 将上述推廣到一般情況為：這就是我們的狀态轉移方程

  F（c，n） = Max（F（c，n-1），F（c-w【n】，n-1）+v【n】）

• 此時我們就可以寫出動态規劃的三要素：
  • 最優子結構：F（c，n-1），F（c-w【n】，n-1）

  • 邊界：其實就是 n = 1 的時候,即隻裝第一個物品的時候，隻需要看容量夠不夠就行了！

    if（n == 1）且 c >= w【1】 則 F（c，n） = v【1】

    if（n == 1）且 c < w【1】 則 F（c，n） = 0

  • 狀态轉移方程：分為四種情況
    • if（n == 1）且 c >= w【1】 則 F（c，n） = v【1】
    • if（n == 1）且 c < w【1】 則 F（c，n） = 0
    • if（n > 1）且 c < w【n】則 F（c，n）= F（c，n-1）
    • if（n > 1）且 c >= w【n】則
    F（c，n）= Max(F（c，n-1）,F（c-w【n】，n-1）+v【n】)

遞歸實作

public static int[] w = {2,3,4,5};

    public static int[] v = {3,4,5,6};
/**
     * 遞歸的寫法
     * @param capacity
     * @param n
     * @return
     */
     
    public static int Package(int capacity, int n){

        if(n == 1 && capacity >= w[0]) return v[0];

        if(n == 1 && capacity < w[0])  return 0;

        if(n > 1 && capacity < w[n - 1])  return Package(capacity, n-1);

        if(n > 1 && capacity >= w[n - 1]){
            int M1 = Package(capacity,n-1);
            int M2 = Package(capacity-w[n-1],n-1) + v[n-1];
            return  Math.max(M1,M2);
        }
        throw new IllegalArgumentException("no result");
    }
           

非遞歸實作

• 這裡非遞歸實作使用了一個備忘錄，也就是定義了一個dp矩陣來存儲計算結果
• dp【i】【j】的含義指的是 j 的容量裝前 i 個物品的最大價值
• 首先對dp矩陣進行初始化，其實也就是将邊界的兩個狀态轉移函數首先進行計算存儲
• 之後分别對物品數量，背包容量進行雙層循環，根據狀态轉移函數來計算存儲，最終傳回結果

/**
     * dp[i][j] 表示j的容量裝前i個物品的最大價值
     * @param capacity
     * @return
     */
    public static int maxPackageValue(int capacity){
        int[][] dp = new int[5][capacity+1];
        //dp矩陣初始化
        for(int j = 1;j < capacity + 1 ;j++){
            if(j < w[0]) dp[1][j] = 0;
            else {
                dp[1][j] = v[0];
            }
        }


        for(int i = 2; i < 5; i++){//物品數量
            for(int j = 1; j < capacity + 1; j++){//容量

                if(j < w[i-1]) dp[i][j] = dp[i-1][j];
                else {
                    int M1 = dp[i-1][j];  //不裝這個
                    int M2 = dp[i-1][j - w[i-1]] + v[i-1];//裝這個
                    dp[i][j] = Math.max(M1,M2);
                }
            }
        }

        return dp[4][capacity];


    }