深入剖析多重背包問題（上篇）

2022 年 7 月 16 日
筆記
動態規劃, 背包問題

深入剖析多重背包問題（上篇）

前言

在前面的兩篇文章當中，我們已經仔細的討論了01背包問題和完全背包問題，在本篇文章當中將給大家介紹另外一種背包問題——多重背包問題，多重背包問題的物品數量介於01背包問題和完全背包問題之間，他的物品的數量是有限個！

多重背包問題介紹

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

注意：上面使用到的字元含義在本篇文章當中都一樣。

多重背包問題跟01背包和完全背包的區別都是在物品的可用次數上，01背包只能使用一次，多重背包可用使用無數次，而多重背包可用使用多次。

背包問題複習——01背包的動態轉移方程

01背包的動態轉移方程

01背包問題當中，我們是使用一個二維數組dp[i][j]進行計算，dp[i][j]表示在只使用前i個物品且背包容量為j的情況下，我們能夠獲得的最大的收益。在這個情況下，我們根據當前背包容量j判斷是否能裝入第i個物品可以得到下面兩個方程：

\[dp[i][j] = \begin{cases}
max(dp[i – 1][j – v[i]] + w[i], dp[i – 1][j]), j \ge v[i]\\
dp[i – 1][j] , j \lt v[i]
\end{cases}
\]

上面01背包的公式的第二條比較簡單，如果背包容量不足以容納第i件物品，那麼只能從前i - 1物品當中選擇了。我們來仔細分析一下第一條公式。

如果當前背包容量可以容納第i個物品，那麼我們就可以選擇第i件物品或者不選擇，我們應該選擇兩種選擇當中收益更大的那個。

如果我們不選擇第i個物品，那麼我們就能夠使用容量為j的背包去選擇前i - 1個物品，這種情況下我們的最大收益為dp[i - 1][j]。
如果選擇第i個物品，那麼我們背包容量還剩下j - v[i]，還可以選擇剩下的i - 1個物品，而且我們的收益需要加上w[i]，因此我們的收益為max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])。

將多重背包轉化成01背包

在多重背包的問題當中，我們對於一種物品我們可以使用多次，比說\(A\)物品我們可以用三次。事實上我們可以將多重背包轉化成01背包，比如我們可以將三個\(A\)物品變成三個不同的物品，所謂不同就是他們的名字不一樣，但是他們的價值和體積都是一樣的，假設\(A\)的體積為\(V_a\)，價值為\(W_a\)，能夠使用的次數為3次，那麼我們可以將其轉化成\(A_1\)，\(A_2\)，\(A_3\)，這三個物品的體積和價值均為\(V_a\)和\(W_a\)，這樣的話\(A\)可以使用3次就轉化成了\(A_1\)、\(A_2\)和\(A_3\)均只能使用一次。通過這種轉換我們就將多重背包轉化成了01背包。

多重背包Java程式碼：

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        ArrayList<Integer> v = new ArrayList<>();
        ArrayList<Integer> w = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int vi = scanner.nextInt();
            int wi = scanner.nextInt();
            int t = scanner.nextInt();
            for (int j = 0; j < t; j++) {
                v.add(vi);
                w.add(wi);
            }
        }
        int[][] dp = new int[v.size() + 1][V+ 1];

        // 對第0行進行初始化操作
        for (int i = v.get(0); i <= V; ++i) {
            dp[0][i] = w.get(0);
        }

        for (int i = 1; i < v.size(); ++i) {
            for (int j = 0; j <= V; ++j) {
                if (j >= v.get(i)) {
                    dp[i][j] = Math.max(dp[i - 1][j],
                                        dp[i - 1][j - v.get(i)] + w.get(i));
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[v.size() - 1][V]);
    }
}

和01背包一樣，我們對多重背包也可以使用單行數組進行優化：

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        ArrayList<Integer> v = new ArrayList<>();
        ArrayList<Integer> w = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int vi = scanner.nextInt();
            int wi = scanner.nextInt();
            int t = scanner.nextInt();
            for (int j = 0; j < t; j++) {
                v.add(vi);
                w.add(wi);
            }
        }
        int[] f = new int[V + 1];
        for (int i = 0; i < v.size(); i++) {
            for (int j = V; j >= v.get(i); j--) {
                f[j] = Math.max(f[j], f[j - v.get(i)] + w.get(i));
            }
        }
        System.out.println(f[V]);
    }
}

多重背包動態轉移方程

在背包容量足夠的情況下，01背包的動態轉移方程為：

\[dp[i][j] =
max(dp[i – 1][j – v[i]] + w[i], dp[i – 1][j]), j \ge v[i]
\]

上述的動態轉移方程是基於每個物品選和不選，那麼對於多重背包來說，如果物品可以選擇\(S\)次，我們可以選擇0次，可以選擇1次，……，可以選擇\(S\)次，我們就需要從這些情況當中選擇收益最大的那次（前提是背包能夠容納下相應次數的物品），因此多重背包的動態轉移方程如下（ \(T = min(S, \frac{V}{v_i})\)，其中\(S\)表示物品能夠選擇的次數，\(v_i\)表示物品的體積，\(V\)表示當前背包的容量）：

\[dp[i][j] =
max\\
\{ \\
dp[i – 1][j], \\
dp[i – 1][j – v[i]] + w[i],\\
dp[i – 1][j – v[i] * 2] + w[i] * 2, \\
…, \\
dp[i – 1][j – v[i] * T] + w[i] * T\\
\}
\]

基於上面的動態轉移方程我們可以得到下面的程式碼：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        int[] w = new int[N];
        int[] v = new int[N];
        int[] t = new int[N];
        int[] f = new int[V + 1];
        for (int i = 0; i < N; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
            t[i] = scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            for (int j = V; j >= v[i]; --j) {
                // 這個循環就表示多重背包的動態轉移公式了
                // 在這段程式碼當中雖然 Math.max的參數只有量
                // 但是有一段循環，將這個循環展開，他表示的
                // 就是多重背包的動態轉移方程
                for (int k = 1; k <= t[i] && j >= v[i] * k; k++) {
                    f[j] = Math.max(f[j], f[j - v[i] * k] + w[i] * k);
                }
            }
        }
        System.out.println(f[V]);
    }
}

總結

在本篇文章當中主要跟大家介紹了多重背包的兩種解決辦法，一種是將多重背包轉化成01背包，另外一種方法是根據多重背包的動態轉移方程去解決問題，可以看出後者的空間複雜度更低，更節約記憶體空間。下期我們用另外一種方法去優化多重背包。

以上就是本篇文章的所有內容了，希望大家有所收穫，我是LeHung，我們下期再見！！！

更多精彩內容合集可訪問項目：//github.com/Chang-LeHung/CSCore

關注公眾號：一無是處的研究僧，了解更多電腦（Java、Python、電腦系統基礎、演算法與數據結構）知識。

Tags: 動態規劃背包問題