2021寒假每日一題《01背包問題》

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

樣例輸入

樣例輸出

解題思路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));
    }
}

解題代碼3-Java：對于解題代碼2的優化

import java.util.*;

public class Main {
    public static int N = 1010;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int v = input.nextInt();
        int[] dp = new int[N];
        for (int i = 1; i <= n; i++) {
            int vi = input.nextInt();
            int wi = input.nextInt();
            for (int j = v; j >= vi; j--) {
                dp[j] = Math.max(dp[j], dp[j - vi] + wi);
            }
        }
        System.out.println(dp[v]);
    }
}