01背包問題

題目來源：背包九講
時間限制：1000ms 記憶體限制：64mb

題目描述

有 \(N\) 件物品和一個容量是 \(V\) 的背包，每件物品只能使用一次，
第 \(i\) 件物品的體積是 \(v_i\)，價值是 \(w_i\)，
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
輸出最大價值，

輸入格式

第一行兩個整數，\(N\)，\(V\)，用空格隔開，分別表示物品數量和背包容積，
接下來有 \(N\) 行，每行兩個整數 \(v_i\),\(w_i\)，用空格隔開，分別表示第 \(i\) 件物品的體積和價值，

輸出格式

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

資料范圍

0 < \(N\),\(V\) ≤ 1000
0 < \(v_i\),\(w_i\) ≤ 1000

樣例輸入

4 5
1 2
2 4
3 4
4 5

樣例輸出

8

解題思路1：暴力破解

嘗試各種可能的商品組合，并找出價值最高的組合，
使用 \(N\) 位二進制字串表示物品是否放入背包，列舉所有的可能，然后算出每種可能的價值，取其最大值輸出，
解法不足：速度非常慢，在只有3件商品的情況下，你需要計算8個不同的集合；當有4件商品的時候，你需要計算16個不同的集合，每增加一件商品，需要計算的集合數都將翻倍，
對于每一件商品，都有選或不選兩種可能，即這種演算法的運行時間是 \(O(2^n)\) ，
IO競賽（例如：藍橋杯）當中，如果實在想不起來動態規劃，可以使用這個方法拿到一部分分數，但是在ACM競賽當中，就不能使用這種方法了，

解題代碼1-Java

import java.util.*;

public class Main {
    static int getSum(int n, int v, StringBuilder binString, int[][] items) {
        int sumV = 0, sumN = 0;
        for (int j = 0; j < n; j++) {
            if (binString.charAt(j) == '1') {
                sumV += items[j][0];
                sumN += items[j][1];
            }
            if (sumV > v) {
                return -1;
            }
        }
        return sumN;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int v = input.nextInt();
        int totalV = 0, totalN = 0;
        int[][] items = new int[n][2];
        for (int i = 0; i < n; i++) {
            items[i][0] = input.nextInt();
            items[i][1] = input.nextInt();
            totalV += items[i][0];
            totalN += items[i][1];
        }
        input.close();
        if (totalV <= v) {
            System.out.println(totalN);
            return;
        }
        int sumN = 0;
        for (long i = 0; i < Math.pow(2, n); i++) {
            StringBuilder binString = new StringBuilder(Long.toBinaryString(i));
            long len = binString.length();
            while (len < n) {
                binString.insert(0, "0");
                len++;
            }
            sumN = Math.max(sumN, getSum(n, v, binString, items));
        }
        System.out.println(sumN);
    }
}

解題思路2：動態規劃

對于動態規劃演算法，可以去這篇文章里學習：經典中的經典演算法:動態規劃(詳細解釋,從入門到實踐,逐步講解)
每個動態規劃都從一個網格開始，
在本題中，網格的各行表示商品，各列代表不同容量的背包（從1到V），
網格最初是空的，你將填充其中的每個格子，網格填滿后，就找到了問題的答案！
比如本題樣例的網格如下圖：

一、畫好網格之后，先來看第一行，

在每個一格子你都要做出一個選擇：放不放進這一行對應的物品，
物品1所占空間為 \(1\) ，也就是說物品1能放進容量為 \(1\) 的這個背包，因此這個單元格包含物品1，所以往第一行第一列中裝入物品1，價值為2，

這行的其他單元格也一樣，別忘了，這是第一行，只有一個物品可供你選擇，換而言之，你假裝現在還沒有打算放進其他物品，
填充完之后如下圖：

此時你很可能心存疑惑：原題說的是容量為5的背包，我們為何要考慮容量為1、2、3、4的背包呢？動態規劃從子問題著手，逐步解決大問題，這里解決的子問題將幫助你解決大問題，
這行表示的是當前的最大價值，并不是最終解，隨著演算法往下執行，將逐步修改最大價值，

二、接下來看第二行，

在第二行中，你有兩種物品選擇，先看第一個單元格，容量為1，之前裝進去的最大的價值為2，
這一個單元格該不該放入第二個物品呢？答案顯然是不行，因為容量為1的口袋無法裝下占空間2的物品，
因此第一列的最大價值保持不變，

接下來看第二行第二列，這個格子所對應背包的容量為2，現在能夠裝下第二個物品了，對比一下價值，比之前決定的物品1價值高，所以將原來的物品1換為物品2，
再看后面的第三列，這個格子容量為3，可以同時裝下物品1和物品2，所以都放進去，
之后的列也進行一樣的操作，最后操作完第二行的結果為：

三、做完第二行，接下來看第三行

以同樣的方式處理物品3，物品3占用空間3，價值為4，
其中在第五列時，容量為5，原本決定的為（物品1+物品2），現在有物品3可以選擇了，所以考慮將物品1換為價值更高的物品3，所以此行第五列結果為8
做完這一步就得到了下面的網格：

四、第四行也一樣

五、最終結果

可以總結得到一個公式：\( cell[i][j](i和j代指行和列) = 兩者中較大的一項 \begin{cases} 1.上一個單元格的值（即：cell[i-1][j]的值） \\ 2.當前物品的價值+剩余空間的價值（即：cell[i-1][j-當前物品的占用空間] + 當前物品的價值） \end{cases} \)
你可以使用這個公式來計算每個單元格的價值，最終的網格將與前一個網格相同，
這里回答前面拋出的問題：為什么要求解子問題？——因為你可以合并兩個子問題的解來得到更大問題的解，
相信看到這里，并且親手推導過網格，應該對動態規劃的狀態轉移方程背后的邏輯有了更深的理解，現在，再回頭看01背包問題的經典描述，并實作代碼，

六、程式實作

宣告一個陣列dp[n+1][v+1]表示初始網格，首行為0，表示不放入任何物品，同時也為了代碼閱讀性，從下標1開始處理，

根據第五步的公式，對于編號為 \(i\) 的物品：

• 如果將\(i\)放入，\(當前背包的最大價值 = 第i號物品的價值 + 出去i號物品占用空間后剩余的空間所能存放的最大價值\)，
  即：\(valueWith\_i = w_i + dp[i-1][j-v_i];\)
• 如果不放入\(i\)，\(當前背包的價值 = 前i-1個物品存放在背包中的最大價值\)，
  即：\(valueWithout\_i = dp[i-1][j];\)
• 最終，\(dp[i][j]\)的結果取兩者的較大值，
  即：\(dp[i][j] = Math.max(valueWith\_i, valueWithout\_i);\)

解題代碼2-Java

import java.util.*;

public class Main {
    static int maxValue(int n, int v, int[][] items) {
        if (n == 0) {
            return 0;
        }
        int[][] dp = new int[n + 1][v + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {
                int valueWith_i = (j - items[i - 1][0] >= 0) ? (items[i - 1][1] + dp[i - 1][j - items[i - 1][0]]) : 0;
                int valueWithout_i = dp[i - 1][j];
                dp[i][j] = Math.max(valueWith_i, valueWithout_i);
            }
        }
        return dp[n][v];
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int v = input.nextInt();
        int totalV = 0, totalN = 0;
        int[][] items = new int[n][2];
        for (int i = 0; i < n; i++) {
            items[i][0] = input.nextInt();
            items[i][1] = input.nextInt();
            totalV += items[i][0];
            totalN += items[i][1];
        }
        input.close();
        if (totalV <= v) {
            System.out.println(totalN);
            return;
        }
        System.out.println(maxValue(n, v, items));
    }
}

標籤：其他

上一篇：力扣刷題（35. 搜索插入位置）

下一篇：2020ICPC 江西省大學生程式設計競賽(A,B,E,G,H,I,K,M)