背包問題之01背包、完全背包

#背包問題九講

0-1背包

題目

有 N 件物品和一個容量是 V 的背包。每件物品隻能使用一次。 第 i 件物品的體積是 vi，價值是 wi。 求解将哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。 輸出最大價值。

輸入格式 :

第一行兩個整數，N，V，用空格隔開，分别表示物品數量和背包容積。 接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分别表示第 i 件物品的體積和價值。

輸出格式 :

輸出一個整數，表示最大價值。

資料範圍 :

0<N,V≤1000

0<vi,wi≤1000

01背包問題的特點在于每個物品隻有一個，這是一道極其經典的動态規劃（dp）問題。動态規劃問題最重要的就是推導出狀态轉移方程。讓我們來分析一下。

“将第i件物品放入背包”，那麼如果隻考慮第i件物品的方式政策，那麼就隻和第i-1件物品有關了，如果是放第i件物品，那麼問題就轉化為：“前i-1件物品放入容量為j的背包中”，此時能夠獲得的最大價值就是f[i-1][j-v[i]]，也就是第i-1件物品放入容量為j（原來的總容量）減去v[i]（第i件物品的占容）産生的最優價值，再加上放通過入第i件物品增加的價值w[i]。 那麼放入第i件物品産生的最大價值就是要在”放“，或者是”不放“中選擇了，”不放“的話，産生的價值就是f[i-1][j]，”放“的話，産生的最大價值就是,f[i-1][j-v[i]]+w[i])。從中選擇較大值

在代碼編寫上，可以對邊界控制進行一些優化，比如數組初始化為N+1，V+1大小的數組，這樣更容易控制邊界條件。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        //存儲物品體積,此處處理為N+1是為了之後邊界更好處理
        int[] v = new int[N+1];
        //存儲物品價值
        int[] w = new int[N+1];
        for(int i = 1;i<=N;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        //此時的dp[i][j] 表示當選擇的物品隻有前i件且物品欄容量為j時的最大價值
        int[][] dp = new int[N+1][V+1];
        dp[0][0] = 0;
        for(int i = 1;i<=N;i++){
            for(int j = 1;j<=V;j++){
                if(j>=v[i]){
                    //不選或者是選擇
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[N][V]);
    }
}
           

此處可以看到，每次狀态轉移的時候隻需要借助上一行的資料，比如dp[i][j]可能需要的是dp[i-1][j-v[i]]和dp[i-1][j]的資料，是以如果從前往後遞推的話，不能得到dp[i-1][j-v[i]]的資料(隻能拿到dp[i][j-v[i]])的資料，是以隻能逆序更新，即更新i再更新i-1。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        //存儲物品體積,此處處理為N+1是為了之後邊界更好處理
        int[] v = new int[N+1];
        //存儲物品價值
        int[] w = new int[N+1];
        for(int i = 1;i<=N;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        int[] dp = new int[V+1];
        for(int i = 1;i<=N;i++){
            //從後往前滾動遞推
            for(int j = V;j>=v[i];j--){
                dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
            }
        }
        System.out.println(dp[V]);
    }
}
           

完全背包問題

題目：

有 N 種物品和一個容量是 V 的背包，每種物品都有無限件可用。第 i 種物品的體積是 vi，價值是 wi。求解将哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。輸出最大價值。

輸入格式

第一行兩個整數，N，V，用空格隔開，分别表示物品種數和背包容積。

接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分别表示第 i 種物品的體積和價值。

輸出格式

輸出一個整數，表示最大價值。

資料範圍

0<N,V≤1000

0<vi,wi≤1000

解析：

完全背包問題，完全是基于01背包的擴充，問題就在于完全背包的物品件數是不限制的。是以相較于前面的01背包的狀态轉移方程：

dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

應該擴充為

dp[i][j]=max{dp[i-1][j],dp[i-1][j-v[i]]+w[i],dp[i-1][j-2v[i]+2w[i]...dp[i-1][j-k*v[i]]+k*w[i]}

但是如果計算的時候使用這種方式的話 複雜度将會擴張。

我們可以看到

dp[i][j-v[i]]=max{dp[i-1][j-v[i]],dp[i-1][j-2v[i]]+w[i],....dp[i-1][j-(k+1)*v[i]]+k*w[i]}

,是以

dp[i][j-v[i]]+w[i]=max{dp[i-1][j-v[i]+w[i],dp[i-1][j-2v[i]]+2w[i]+....+dp[i-1][j-k*v[i]]+k*w[i]}

是以，可以得到

dp[i][j]=max{dp[i-1][j],dp[i][j-v[i]]+w[i]}

這一個狀态轉移公式。

代碼：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        //存儲物品體積,此處處理為N+1是為了之後邊界更好處理
        int[] v = new int[N+1];
        //存儲物品價值
        int[] w = new int[N+1];
        for(int i = 1;i<=N;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        int[][] dp = new int[N+1][V+1];
        for(int i = 1;i<=N;i++){
            for(int j = 1;j<=V;j++){
                if(v[i]<=j){
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[N][V]);
    }
}
           

至于完全背包問題的優化，就交給讀者自己去嘗試一下吧，原理和之前的01背包的優化基本上一緻。寫出代碼的小夥伴可以到

https://www.acwing.com

該網站的Online Judge對自己的代碼進行評判。