動态規劃：非0-1背包問題（java）——05

非01背包問題

• 個人認為初學者還是先弄懂01背包，再來看非01背包，這樣思路會清楚很多，
• 動态規劃：0-1背包問題（遞歸和非遞歸java實作）

問題描述

• 一個旅行者随身攜帶一個背包. 可以放入背包的物品有n 種, 每種物品的重量和價值分别為 wi , vi . 如果背包的最大重量限制是 b, 每種物品可以放多個. 怎樣選擇放入背包的物品以使得背包的價值最大 ? 不妨設上述 wi , vi , b 都是正整數.

• 執行個體：

  n = 4， b =10（背包容量為10，物品數量為4）

v1	v2	v3	v4
1	3	5	6

w1	w2	w3	w4
2	3	4	5

算法思路

• 其實非01背包問題和01背包問題思路都是一樣的，隻不過在狀态轉移方程上有所差別
• 确定子問題：背包問題的子問題就是容量為B的背包裝前n種物品的最大價值，我們設此函數為F（B，n），這裡的執行個體B = 10， n = 4
• 看最後一步：在我們已經求出F（10,3）的條件下，我們應該如何求F（10,4），很明顯，隻有兩個選擇，裝第四種物品和不裝第四種物品，如果裝第四種物品，就還會分為多種情況，那就是裝多少個第四個物品
  • 不裝第四種物品：此時最大價值為M1 = F（10,3）
  • 裝第四種物品：那麼就要分出一定的容量裝這個物品，剩餘容量裝前3種物品
    • 裝一個：M2 = F（10-5，3）+ 6 = F（5,3） + 6
    • 裝兩個：M3 = F（10-5*2,3）+ 6 * 2 = F（0,3）+12
    • 裝三個：總共的容量為10，不可能裝三個第四種物品，是以不存在
  • 此時F（10,4） = Max（M1, M2, M3）
• 狀态轉移方程：這裡借用我們老師上課課件的方程，其實就是不斷測試裝第n個物品裝0個，裝1個，裝2個，裝xxx個的最大價值，然後取最大值就行了

  

• 這裡再來梳理一下我們的思路：例如我們要求F（B，n）
  • 首先我們要判斷B是否大于w【n】
    • 若B < w【n】，那麼F（B，n） = F（B，n-1）
    • 若B > w【n】，則說明B容量可以放第n種物品，并且可以放 B / w【n】 = x 個
      • 若放1個：M1 = F（B - w【n】，n -1） + v【n】
      • 若放2個：M2 = F（B - w【n】* 2， n - 1 ）+ v【n】 * 2
      • ····················
      • 若放x個：Mx = F（B - w【n】* x，n - 1） + v【n】* 2
      • 最終F（B，n） = Max（M1, M2, M3,…Mx）

DP矩陣的存儲含義

• dp【i】【j】表示 j 容量裝前 i 個物品的最大價值。這裡定義dp【5】【11】
• 首先要确定邊界，也就是i = 1 的時候，我們需要對矩陣進行初始化
• dp【0】【x】和dp 【x】【0】都設定為0

• 

• 最終的dp矩陣如下

• 

java實作

public static int[] v = new int[]{1,3,5,6};
public static int[] w = new int[]{2,3,4,5};


public static int caculateMaxValue(){
    int dp[][] = new int[5][11];

    //初始化 确定邊界
    for(int j = 1; j < 11; j++){
        if(j / w[0] == 0){
            dp[1][j] = 0;
        }else {
            dp[1][j] = v[0]*(j / w[0]);
        }
    }

   
    for(int i = 2; i < 5; i++){

        for(int j = 1; j < 11; j++){
            int xi = j / w[i-1];
            if(xi == 0){ //目前容量裝不下這種物品
                dp[i][j] = dp[i-1][j];
            }else {
                 dp[i][j] = dp[i-1][j]; //假設最大值是不裝這個物品
                while(xi != 0){//不斷測試裝1個 2個 3個
                	//狀态轉移方程
                    int temp = dp[i - 1][j - xi*w[i-1]] + xi*v[i-1];
                    if( temp > dp[i][j]) dp[i][j] = temp;
                    xi--;
                }
            }


        }

    }

    return dp[4][10];

}
           

總結

• 非01背包問題其實和01背包問題很想像，思路也是一樣的，隻不過是每次要在最裡層多一個循環，不斷測試裝0個 ，1個， 2個， x個的最大價值！