Skip to content

背包 DP (Knapsack DP)

0-1 背包問題

0-1 背包問題

給定 個物品的重量 和價值 ，和一個容量為 的背包。選取若干件物品放入背包，在不超過背包容量的情況下，背包內物品價值總和最大為何?

每種物品有兩個狀態不放與放，可對應二進位的 和 ，故稱為「0-1 背包問題」。

題目有三項資料，物品個數、物品重量、物品價值，利用這些資料設計出狀態式：

  • 狀態： 代表前 樣物品在重量總和 的情況下，物品價值總和最大值。
  • 初始狀態： 。

當算好 個物品的狀態，對於第 個物品有兩種選擇

  • 不放：重量和價值不變 。
  • 放：重量 ，價值 。

轉移式就由上面兩種選擇歸納出：

  • 。

以下為利用二維陣列儲存答案的範例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int dp[MXN + 1][MXW + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= MXN; ++i)
{
    for (int j = 0; j < w[i]; ++j)
    {
        dp[i][j] = dp[i - 1][j];
    }
    for (int j = w[i]; j <= MXW; ++j)
    {
        dp[i][j] = max(dp[i - 1][j − w[i]] + v[i], dp[i - 1][j]);
    }
}

cout << dp[MXN][MXW] << '\n';

滾動陣列

空間複雜度 ，採用「滾動陣列」，可以降低空間複雜度

由上圖可得知，當在計算 時，只會用到上一列的資料，因此我們的需要陣列大小降到 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int dp[2][MXW + 1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; ++i)
{
    for (int j = 0; j < w[i]; ++j)
    {
        dp[i & 1][j] = dp[(i & 1) ^ 1][j];
    }
    for (int j = w[i]; j <= MXW; ++j)
    {
        dp[i & 1][j] =
            max(dp[(i & 1) ^ 1][j − w[i]] + v[i], dp[(i & 1) ^ 1][j]);
    }
}

再來，如果我們將 當中的 由大到小計算。

會發現計算 時， 也不會用到，可以將 覆蓋到 上面。我們可以再次縮小陣列，變成大小為 的一維陣列。

1
2
3
4
5
6
7
8
9
int dp[MXW + 1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; ++i)
{
    for (int j = MXW; j >= w[i]; --j)
    {
        dp[j] = max(dp[j − w[i]] + v[i], dp[j]);
    }
}
滾動陣列

覆蓋不會用到的資訊，降低記憶體使用量。

0-1 背包問題時間複雜度 ，空間複雜度 。

背包問題另一種狀態式

這題的 範圍在 ，用上述的狀態式肯定 TLE ，因此我們將狀態式改成：

  • 狀態： 代表前 樣物品在價值總和為 的情況下，重量總和最小值。
  • 初始狀態： 。

轉移式改成：

最後找出：

技巧：表示(負)無限大

(負)無限大只要設成一個比最大(小)答案還要大(小)的值就行了。

無限背包問題

無限背包問題

給定 種物品的重量 和價值 ，和一個容量為 的背包。每種物品可選取任意個放入背包，在不超過背包容量的情況下，背包內物品價值總和最大為何?

無限背包問題和 0-1 背包問題差異在於無限背包的物品可以選無限多個。

無限背包問題和 0-1 背包問題的狀態式相同，以下為轉移式：

可以簡化成：

  • 。
  • 。

為什麼可以這樣優化？是因為當 當中的 由小到大計算時， 已被 更新過，那麼 就是選擇第 種物品數次的最佳結果。

換言之，我們通過局部最優子結構的性質重複使用了之前的枚舉過程，優化了枚舉的複雜度。(from 背包 DP - OI Wiki )

下面為範例程式碼，一樣有用到滾動陣列的技巧：

1
2
3
4
5
6
7
8
9
int dp[MXW + 1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; ++i)
{
    for (int j = w[i]; j <= MXW; ++j)
    {
        dp[j] = max(dp[j − w[i]] + v[i], dp[j]);
    }
}

無限背包問題時間複雜度 ，空間複雜度 。

例題練習