完全背包轉化為多重背包

• 2022 年 8 月 15 日
• 筆記
• 動態規劃, 算法, 背包問題

完全背包轉化為多重背包

前言

在本篇文章當中主要給大家介紹如何將完全背包問題轉化成多重背包問題，在前面的文章完全背包當中，我們仔細的介紹了完全背包的狀態轉移方程、根據狀態轉移方程如何完成代碼以及多重背包的數組優化的原理，為什麼這種優化能夠有效！本篇文章主要專註於如何將完全背包轉化成多重背包。如果你還不了解多重背包可以先閱讀深入剖析多重背包問題（上篇）和深入剖析多重背包問題（下篇）。

完全背包問題

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

完全背包問題和01背包的唯一區別就在於物品的個數，在01背包當中所有的物品只有一件，也就只能使用一次。而在完全背包當中物品可以使用無限多次。

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

這個問題還是比較簡單，我們直接從圖中看，我們可以選擇五個A或者兩個B一個A，可以產生最大的收益，最大收益為10。

動態轉移方程

在前面的文章完全背包當中我們仔細介紹了完全背包的動態轉移方程。我們用一個二位數組dp[i][j]表示當只使用前i個物品且背包容量為j的時候，我們能夠獲取的最大的收益。

和01背包問題一樣首先對於第i個物品，首先需要判斷背包是否能夠容納（v[i]表示第i件物品的體積，w[i]表示第i件物品的價值）：

• 如果背包的容量大於等於第i個物品的體積，那我們就有兩種選擇：
  • 將第i個物品放入背包當中，但是在這裡需要注意的一點是完全背包的物品有無數件，因此當我們選擇之後我們的轉移方程為dp[i][j - v[i]] + w[i]，這裡不是i-1而是i，因為第i件物品有無數件。
  • 不將第i個物品放入背包當中，那麼我們就能夠使用容量為j的背包去選擇前i - 1個物品，這種情況下我們的最大收益為dp[i - 1][j]。
• 如果背包容量小於第i件物品的體積，我們就不能夠選擇第i件物品了，這種情況下我們的最大收益為dp[i - 1][j]。

基於上面的分析我們可以知道完全背包問題的動態轉移方程為：

根據上面的狀態轉移方程，我們的核心代碼如下（其中N表示物品的個數，V表示背包的容量，w[i]表示第i個物品的價值，v[i]表示第i個物品所佔的體積）：

int backpack() {
  for (int i = 1; i < N; ++i) {
    for (int j = 0; j <= V; ++j) {
        if (j >= v[i]) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
        }
        else {
            dp[i][j] = dp[i - 1][j];
        }
    }
	}
  return dp[V];
}

但是上面的代碼我們可以進行數組優化，優化之後的代碼如下（如果你還不是很清楚優化原理的話，你可以閱讀完全背包當中的數組優化小節）：

int backpack() {
	for (int i = 0; i < N; ++i) {
		for (int j = v[i]; j <= V; ++j) {
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
	return dp[V];
}

問題轉化

我們知道完全背包問題當中的物品是可以無限次使用的，但是實質上我們不可能拿無限個物品，因為我們的背包容量是有限的，假如我們的背包容量為V物品的體積為v，那麼我們能夠拿的最大的個數就是：

因此我們這樣就將一個完全背包問題轉化成了多重背包問題，每一個物品的最大數量就是：

上面的公式簡單的說來就是拿的所有的物品所佔的體積不能超過背包的容量。因此我們可以重寫完全背包的狀態轉移方程：

其中 \(T_i = \lfloor\frac{V}{v_i}\rfloor\)。

因此完全背包轉多重背包的代碼如下（進行數組優化之後的代碼，如果你還不了解數組的優化，可以先閱讀完全背包、深入剖析多重背包問題（上篇）和深入剖析多重背包問題（下篇）當中數組優化的小節）：

#include <iostream>

using namespace std;

#define MAX_LENGTH 2000

int N, V;

int values[MAX_LENGTH];
int volumes[MAX_LENGTH];
int dp[MAX_LENGTH];

void complete_backpack() {
  // 前面兩側循環和正常的 dp 循環一樣
  for (int i = 0; i < N; ++i) {
    for (int j = V; j >= volumes[i]; j--) {
      // 這裡就是根據背包容量進行限制了 j 肯定要大於等於拿的所有物品的容量
      for(int k = 1; j >= volumes[i] * k; k++) {
        dp[j] = max(dp[j], dp[j - volumes[i] * k] + values[i] * k);
      }
    }
  }
}


int main() {
  cin >> N >> V;
  for (int i = 0; i < N; i++) {
    cin >> volumes[i] >> values[i];
  }
  complete_backpack();
  printf("%d", dp[V]);
  return 0;
}

總結

在本篇文章當中主要介紹了入和將完全背包轉化成多重背包，我們可以知道完全背包的時間複雜度為\(O(NV)\)，但是如果將完全背包轉化成多重背包之後時間複雜度為\(O(NVM)\)，其中M表示平均每個物品能拿的最大的個數，因此可以知道其實不必將完全背包轉化成多重背包，但是可以擴展我們的思維。

將完全背包轉化成多重背包的最核心的就是背包容量的限制，我們可以通過背包容量有限制這一條件，知道我們能夠拿的最大的物品數量，從而將完全背包轉化成多重背包問題。

以上就是本篇文章的所有內容了，我是LeHung，我們下期再見！！！更多精彩內容合集可訪問項目：//github.com/Chang-LeHung/CSCore

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