二重背包問題 動态規劃求解

多重背包問題

考慮最一般形式的背包問題（動态規劃算法)，如下：

輸入一個整數W和V,W和V代表背包可容納的最大重量和最大體積；

輸入N個整數，代表N種物品；每個物品有4種屬性，分别是重量、體積、價值、數量；

以下依次輸入的N行數，每行的四個數分别代表四種屬性；

求可以獲得的最大價值；

sample input:

215 130

10

12 9 16 4

16 4 5 4

15 12 11 3

7 17 5 2

12 9 16 4

13 2 17 1

19 14 6 5

9 8 1 2

14 8 6 5

18 1 12 3

sample output:

219

//s 數組存儲了物品的四個屬性，w,v分别為最大載重和最大容納的體積

1.最為基本的考慮方式是使用一個三維數組來存儲：

f[i][j][k]表示考慮前i個物品，背包載重為j，容納體積為k時可獲得的最大價值

public static int F(int[][] s, int w, int v, int n){
        int[][][] f = new int[n + 1][w + 1][v + 1];
        int i, j, k, r;
        for(i = 1; i <= n; i ++){
            for(j = 1; j <= w; j++){
                for(k = 1; k <= v; k ++){
                        for (r = 0; r <= s[i - 1][3] && j - r * s[i - 1][0] >= 0 && k - r * s[i - 1][1] >= 0; r++) {
                            f[i][j][k] = Math.max(f[i - 1][j][k], f[i - 1][j - r * s[i - 1][0]][k - r * s[i - 1][1]] + s[i - 1][2] * r);
                        }
                }
            }
        }
           

2、上述方式的記憶體占用較大，發現疊代時隻用了前一組資料和目前的資料，故可以考慮如下的簡化：

倒序周遊時之前的資料還沒被更新，不用額外去存儲一次

public static int H(int[][] s, int w, int v, int n){
        int[][] f = new int[w + 1][v + 1];
        int i, j, k, r;
        for(i = 1; i <= n; i ++){
            for(j = w; j >=0; j --) {
                for (k = v; k >= 0; k--) {
                    r = 0;
                    while (r <= s[i - 1][3] && j - r * s[i - 1][0] >= 0 && k - r * s[i - 1][1] >= 0) {
                        f[j][k] = Math.max(f[j][k], f[j - r * s[i - 1][0]][k - r * s[i - 1][1]] + s[i - 1][2] * r);
                        r ++;
                    }
                }
            }
        }
        return f[w][v];
    }
           

3、對于資料量較大的問題，2中代碼運作相對較慢，故考慮用二進制優化

擷取輸入并存儲物品屬性的時候改用Arraylist,友善進行二進制優化

Scanner input = new Scanner(System.in);
        ArrayList<int[]> tab = new ArrayList<>();
        int W = input.nextInt();
        int V = input.nextInt();
        int n = input.nextInt();
        int num, t;
        int[] p = new int[3];
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < 3; j ++)
                p[j] = input.nextInt();
            num = input.nextInt();
            t = 1;
            while(num - t > 0){
                int[] temp = new int[3];
                for(int k = 0; k < 3; k ++)
                    temp[k] = p[k] * t;
                tab.add(temp);
                num -= t;
                t <<= 1;
            }
            if(num - t <= 0){
                int[] temp = new int[3];
                for(int k = 0; k < 3; k ++)
                    temp[k] = p[k] * num;
                tab.add(temp);
            }
        }
        input.close();
           

進一步的DP計算：

public static int F(ArrayList<int[]> s, int w, int v){
        int[][] f = new int[w + 1][v + 1];
        int i, j;
        for(int[] p : s){
            for(i = w; i >= 0; i --){
                for(j = v; j >= 0; j--){
                    if(i - p[0] >=0 && j - p[1] >=0)
                        f[i][j] = Math.max(f[i][j], f[i - p[0]][j - p[1]] + p[2]);
                }
            }
        }
        return f[w][v];
    }
           

//二進制優化的想法來源于其他大佬，筆者發現網上絕大多數是c++代碼，沒有發現java版本的，故嘗試寫了個java版本的