你真的懂01背包問題嗎？01背包的這幾問你能答出來嗎？

關于01背包的幾個問題

• 背包問題的動態轉移方程是怎么來的？

• 你能解釋背包問題的兩個for回圈的意義嘛？

• 為什么需要兩個for回圈，一個回圈行不行？

• 01背包問題的for回圈一定要從0開始嗎？

• 01背包滾動陣列的優化原理是什么？

• 01背包只用不用二維陣列只用一位陣列的依據是什么？

這些問題在閱讀完本文之后你將會得到答案！

01背包問題介紹

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

比如下面的4個物品，背包能夠承受的最大重量為5，我們應該如何選擇，使得我們獲得的總價值最大：

這個問題還是比較簡單，我們直接看就知道選擇物品B和物品C得到的價值最大，那么我們如何設計一個演算法去實作這個問題呢？首先對于每一個物品都有兩種情況，選擇和不選擇，我們需要選擇兩種情況當中能夠獲取最大價值的那種情況，

01背包問題動態轉移方程

首先我么先要確定一個資訊就是沒件物品只有一件，選完就沒有了，如果我們的背包當中還有剩余容量可以放下某個物品，那么對于這個物品我們就有兩種選擇：選或者不選，

我們定義陣列dp[i][j]，其含義是對于前i件物品，在我們的背包容量為j的情況下我們能夠獲得的最大的收益，如果我們有N件物品，背包容量為V，那么我們能夠獲得的最大價值為dp[N][V]，因為他表示的是對于前N個物品，在背包容量為V的情況下我們能夠獲取到的最大的價值，我們可以得到下面的公式：

• 第一種情況（背包容量大于等于第i件物品的體積v[i]時）：
  • 在這種情況下我們對于第i件物品有兩種選擇，一種是將其放入背包當中，另外一種就是不選他，那么我們就可以使用容量為j的背包在前i-1件物品進行選擇，
  • 如果我們選第i件物品，那么我們背包剩下的容量就為j - v[i]，我們還能選擇的物品就是前i - 1個物品，這個情況下能夠獲得的最大的收益為\(dp[i - 1][j - v[i]]\)，再加上我們選擇的第i件物品的價值，我們選擇第i件物品能夠獲得的總收益為dp[i - 1][j - v[i]] + w[i]，
  • 如果我們不選擇第i件物品，那么我們背包剩余容量仍然為j，而且我們只能從前i - 1 個商品當中進行選擇，那么我們最大的收益就為dp[i - 1][j]，
• 第二種情況（背包容量小于第i件物品的體積v[i]時）：
  • 這種情況下我們只能夠選擇前i - 1個商品，因此我們能夠獲取的最大收益為dp[i - 1][j]，

01背包資料依賴問題分析

在上文當中我們已經分析出來了我們的動態轉移方程：

根據上面兩個公式分析，我們知道要想解出dp[i][j]的值，我們首先需要知道dp[i - 1][j - v[i]]的值和dp[i - 1][j]的值，他們之間的依賴關系如下圖所示：

基于上面的資料依賴關系，我們知道我們如果想求dp[N][V]的值，首先要求出dp陣列第N - 1行的所有的值，因為dp[N][V]依賴dp[N - 1][V]，而且可能依賴dp[N - 1][i]的值（i大于等于0，小于V），而dp[N - 1][V]又依賴dp[N - 2][V]......
根據上面的分析程序，如果我們想計算出dp[N][V]的結果，那就需要從第1行開始往后計算，一直算到第N`行，因此我們可以寫出下面的代碼：

Java版本：

import java.util.Scanner;

public class Main {

  public static int backpack(int[] w, int[] v, int N, int V) {
    int[][] dp = new int[N + 1][V + 1];
    // 初始化
    for (int i = v[1]; i <= V; ++i) {
      dp[1][i] = w[1];
    }
    // 第一行已經初始化 從第二行開始
    for (int i = 2; i <= N; ++i) {
      for (int j = 0; j <= V; ++j) {
        if (j >= v[i])
          dp[i][j] = Math.max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
        else
          dp[i][j] = dp[i - 1][j];
      }
    }
    return dp[N][V];
  }

  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 + 1];
    int[] v = new int[N + 1];
    for (int i = 1; i <= N; i++) {
      v[i] = scanner.nextInt();
      w[i] = scanner.nextInt();
    }
    System.out.println(backpack(w, v, N, V));
  }
}

C++版本：

#include <iostream>
using namespace std;

#define L 20000
int w[L]; // 物品價值
int v[L]; // 物品體積
int dp[L][L];

int N; // 物品數量
int V; // 背包的體積

int backpack() {

	// 初始化
	for (int i = v[1]; i <= V; ++i) {
		dp[1][i] = w[1];
	}
	// 第一行已經初始化 從第二行開始
	for (int i = 2; i <= N; ++i) {
		for (int j = 0; j <= V; ++j) {
			if (j >= v[i])
				dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
			else
				dp[i][j] = dp[i - 1][j];
		}
	}
	return dp[N][V];
}

int main() {
	cin >> N >> V;
	for (int i = 1; i <= N; ++i) {
		cin >> v[i] >> w[i];
	}
	cout << backpack();
	return 0;
}

從上圖看我們在計算第i的資料的時候我們只依賴第i - 1行，我們在第i行從后往前遍歷并不會破壞動態轉移公式的要求，

因此下面的代碼也是正確的：

public static int backpack(int[] w, int[] v, int N, int V) {
    int[][] dp = new int[N + 1][V + 1];
    // 初始化
    for (int i = v[1]; i <= V; ++i) {
        dp[1][i] = w[1];
    }
    // 第一行已經初始化 從第二行開始
    for (int i = 2; i <= N; ++i) {
        // 這里是從末尾到0
        // 前面是從0遍歷到末尾
        for (int j = V; j >= 0; --j) {
            if (j >= v[i])
                dp[i][j] = Math.max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[N][V];
}

01背包問題優化——滾動陣列

我們在解決背包問的時候我們是開辟了一個二維陣列dp，那么我們能不能想斐波拉契數列那樣降低演算法的空間復雜度呢？我們已經很清楚了我們在計算dp資料的時候進行計算的時候只使用了兩行資料，那么我們只需要申請兩行的空間即可，不需要申請那么大的陣列空間，計算的時候反復在兩行資料當中交替計算既可，比如說我們已經計算好第一行的資料了（初始化），那么我們可以根據第一行得到的結果得到第二行，然后根據第二行，將計算的結結果重新存盤到第一行，如此交替反復，像這種方法叫做滾動陣列，

下面的代碼當中dp陣列是從第0行開始使用的，前面的代碼是從第一行開始的，

import java.util.Scanner;

public class Main {


    public static int backpack(int[] v, int[] w, int V) {
      int N = w.length;
      int[][] dp = new int[2][V + 1];
      for (int i = v[0]; i < V; ++i) {
        dp[0][i] = w[0];
      }
      for (int i = 1; i < N; ++i) {
        for (int j = V; j >= 0; --j) {
          if (j >= v[i])
            dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j],
                dp[(i - 1) % 2][j - v[i]] + w[i]);
          else
            dp[i % 2][j] = dp[(i - 1) % 2][j];
        }
      }
      return dp[(N - 1) % 2][V];
  }


  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];
    for (int i = 0; i < N; i++) {
      v[i] = scanner.nextInt();
      w[i] = scanner.nextInt();
    }
    System.out.println(backpack(v, w, V));
  }
}

背包空間再優化——單行陣列和它的遍歷順序問題

我們還能繼續壓縮空間嗎??？我們在進行空間問題的優化的時候只要不破壞動態轉移公式，只需要我們進行的優化能夠滿足dp[i][j]的計算在它所依賴的資料之后計算即可，

import java.util.Scanner;

public class Main {

  public static int backpack(int[] v, int[] w, int V) {
    int N = w.length;
    int[] dp = new int[V + 1];
    for (int i = v[0]; i < V; ++i) {
      dp[i] = w[0];
    }
    for (int i = 1; i < N; ++i) {
      for (int j = V; j >= v[i]; --j) {
        dp[j] = Math.max(dp[j - v[i]] + w[i], dp[j]);
      }
    }
    return dp[V];
  }

  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];
    for (int i = 0; i < N; i++) {
      v[i] = scanner.nextInt();
      w[i] = scanner.nextInt();
    }
    System.out.println(backpack(v, w, V));
  }
}

我們現在來好好分析一下上面的代碼：

• 根據動態轉移公式dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])我們知道，第i行的第j個資料只依賴第i - 1行的前j個資料，跟第j個資料之后的資料沒有關系，因此我們在使用一維陣列的時候可以從后往前計算（且只能從后往前計算，如果從前往后計算會破壞動態轉移公式，因為第j個資料跟他前面的資料有依賴關系，跟他后面的資料沒有依賴關系）就能夠滿足我們的動態轉移公式，

• 如果我們從在使用單行陣列的時候從前往后計算，那么會使得一維資料前面部分資料的狀態從i - 1行的狀態變成第i行的狀態，像下面這樣，

但是一維陣列當中后部分的資料還是i - 1行的狀態，當我們去更新他們的時候他們依賴前面部分資料的i - 1行的狀態，但是他們已經更新到第i的狀態了，因此破壞了動態規劃的轉移方程，但是如果我們從后往前進行遍歷那么前面的狀態始終是第i - 1行的狀態，因此沒有破壞動態規劃的轉移方程，因此我們需要從后往前遍歷，

問題答案

如果你已經看懂上面所談論到的內容的話，關于前面的幾個問題相信你已經有了答案，上面那些問題最終涉及到的就是01背包問題的動態轉移方程了，我們在寫代碼的時候一定不能破壞動態轉移方程，也就是要滿足動態轉移方程的依賴關系，即第i行的第j個資料只依賴第i - 1行的前j個資料，跟第j個資料之后的資料沒有關系，

• 背包問題的兩個for回圈的意義：
  • 因為我們需要解出dp陣列當中第N行第V列的資料，所以我們需要解出二維陣列當中所有的資料，因此我們需要進行二維陣列的遍歷，進行一維遍歷不行，
• 01背包問題的for回圈一定要從0開始嗎？
  • 不一定，我們只需要滿足動態轉移方程的資料依賴要求就行，不管是從前往后還是從后往前我們在使用二維dp陣列的遍歷的時候都可以滿足資料依賴的要求，但是我們如果使用一維陣列的時候就一定要從后往前遍歷，因為如果從前往后遍歷，第i行狀態會覆寫第i - 1行的狀態，而陣列后面的資料需要i - 1行狀態的資料，而它有被覆寫了因此不行，
• 其余問題的答案在閱讀完本文之后相信你心里已經很清楚了！！！

動態規劃為什么叫動態規劃

首先我們需要明白什么是規劃所謂的規劃 就是尋找最優值的程序，比如說我們在旅行的時候做規劃就是為了又更好旅行體驗，而我們在做演算法題的時候需要找到最好的結果，比如在背包問題當中我們要找到價值最大的一種選擇，這也是一種規劃，那為什么是動態的呢？所謂動態就是我們在尋找最優值的程序當中，選擇是變化的，比如說對于背包問題的公式dp[i][j] = max(dp[i - 1][j - v[i] + w[i], dp[i - 1][j])我們在計算出結果之前并不知道那種選擇好，因為我們要選擇兩者中間值較大的哪個選擇，這就是動態選擇的程序！所以動態規劃被稱作動態規劃！

總結

本篇文章主要帶大家從0開始剖析01背包問題，主要分享一些基本但經常被忽略的問題，比如二重回圈是如何被寫出來的，for回圈的順序問題，陣列空間優化問題的原理，用一維陣列解決01背包問題！希望大家有所識訓，我是LeHung，我們下期再見！！！

更多精彩內容合集可訪問專案：https://github.com/Chang-LeHung/CSCore

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

標籤：其他

上一篇：Hash 哈希表和演算法思路詳解

下一篇：lora和lorawan物聯網無線傳輸技術