跳转至

揹包 DP

前置知識：動態規劃部分簡介。

引入

在具體講何為「揹包 dp」前，先來看如下的例題：

「USACO07 DEC」Charm Bracelet

題意概要：有 \(n\) 個物品和一個容量為 \(W\) 的揹包，每個物品有重量 \(w_{i}\) 和價值 \(v_{i}\) 兩種屬性，要求選若干物品放入揹包使揹包中物品的總價值最大且揹包中物品的總重量不超過揹包的容量。

在上述例題中，由於每個物體只有兩種可能的狀態（取與不取），對應二進制中的 \(0\) 和 \(1\)，這類問題便被稱為「0-1 揹包問題」。

0-1 揹包

解釋

例題中已知條件有第 \(i\) 個物品的重量 \(w_{i}\)，價值 \(v_{i}\)，以及揹包的總容量 \(W\)。

設 DP 狀態 \(f_{i,j}\) 為在只能放前 \(i\) 個物品的情況下，容量為 \(j\) 的揹包所能達到的最大總價值。

考慮轉移。假設當前已經處理好了前 \(i-1\) 個物品的所有狀態，那麼對於第 \(i\) 個物品，當其不放入揹包時，揹包的剩餘容量不變，揹包中物品的總價值也不變，故這種情況的最大價值為 \(f_{i-1,j}\)；當其放入揹包時，揹包的剩餘容量會減小 \(w_{i}\)，揹包中物品的總價值會增大 \(v_{i}\)，故這種情況的最大價值為 \(f_{i-1,j-w_{i}}+v_{i}\)。

由此可以得出狀態轉移方程：

\[ f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i}) \]

這裏如果直接採用二維數組對狀態進行記錄，會出現 MLE。可以考慮改用滾動數組的形式來優化。

由於對 \(f_i\) 有影響的只有 \(f_{i-1}\)，可以去掉第一維，直接用 \(f_{i}\) 來表示處理到當前物品時揹包容量為 \(i\) 的最大價值，得出以下方程：

\[ f_j=\max \left(f_j,f_{j-w_i}+v_i\right) \]

務必牢記並理解這個轉移方程，因為大部分揹包問題的轉移方程都是在此基礎上推導出來的。

實現

還有一點需要注意的是，很容易寫出這樣的 錯誤核心代碼：

1
2
3
4
5
for (int i = 1; i <= n; i++)
  for (int l = 0; l <= W - w[i]; l++)
    f[l + w[i]] = max(f[l] + v[i], f[l + w[i]]);
// 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]], f[i - 1][l] + w[i]),
// f[i][l + w[i]]); 簡化而來

1
2
3
4
5
for i in range(1, n + 1):
    for l in range(0, W - w[i] + 1):
        f[l + w[i]] = max(f[l] + v[i], f[l + w[i]])
# 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]], f[i - 1][l] + w[i]),
# f[i][l + w[i]]) 簡化而來

這段代碼哪裏錯了呢？枚舉順序錯了。

仔細觀察代碼可以發現：對於當前處理的物品 \(i\) 和當前狀態 \(f_{i,j}\)，在 \(j\geqslant w_{i}\) 時，\(f_{i,j}\) 是會被 \(f_{i,j-w_{i}}\) 所影響的。這就相當於物品 \(i\) 可以多次被放入揹包，與題意不符。（事實上，這正是完全揹包問題的解法）

為了避免這種情況發生，我們可以改變枚舉的順序，從 \(W\) 枚舉到 \(w_{i}\)，這樣就不會出現上述的錯誤，因為 \(f_{i,j}\) 總是在 \(f_{i,j-w_{i}}\) 前被更新。

因此實際核心代碼為

1
2
for (int i = 1; i <= n; i++)
  for (int l = W; l >= w[i]; l--) f[l] = max(f[l], f[l - w[i]] + v[i]);

1
2
3
for i in range(1, n + 1):
    for l in range(W, w[i] - 1, -1):
        f[l] = max(f[l], f[l - w[i]] + v[i])
例題代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
using namespace std;
const int maxn = 13010;
int n, W, w[maxn], v[maxn], f[maxn];

int main() {
  cin >> n >> W;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];  // 读入数据
  for (int i = 1; i <= n; i++)
    for (int l = W; l >= w[i]; l--)
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];  // 状态方程
  cout << f[W];
  return 0;
}

完全揹包

解釋

完全揹包模型與 0-1 揹包類似，與 0-1 揹包的區別僅在於一個物品可以選取無限次，而非僅能選取一次。

我們可以借鑑 0-1 揹包的思路，進行狀態定義：設 \(f_{i,j}\) 為只能選前 \(i\) 個物品時，容量為 \(j\) 的揹包可以達到的最大價值。

需要注意的是，雖然定義與 0-1 揹包類似，但是其狀態轉移方程與 0-1 揹包並不相同。

過程

可以考慮一個樸素的做法：對於第 \(i\) 件物品，枚舉其選了多少個來轉移。這樣做的時間複雜度是 \(O(n^3)\) 的。

狀態轉移方程如下：

\[ f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k) \]

考慮做一個簡單的優化。可以發現，對於 \(f_{i,j}\)，只要通過 \(f_{i,j-w_i}\) 轉移就可以了。因此狀態轉移方程為：

\[ f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i) \]

理由是當我們這樣轉移時，\(f_{i,j-w_i}\) 已經由 \(f_{i,j-2\times w_i}\) 更新過，那麼 \(f_{i,j-w_i}\) 就是充分考慮了第 \(i\) 件物品所選次數後得到的最優結果。換言之，我們通過局部最優子結構的性質重複使用了之前的枚舉過程，優化了枚舉的複雜度。

與 0-1 揹包相同，我們可以將第一維去掉來優化空間複雜度。如果理解了 0-1 揹包的優化方式，就不難明白壓縮後的循環是正向的（也就是上文中提到的錯誤優化）。

「Luogu P1616」瘋狂的採藥

題意概要：有 \(n\) 種物品和一個容量為 \(W\) 的揹包，每種物品有重量 \(w_{i}\) 和價值 \(v_{i}\) 兩種屬性，要求選若干個物品放入揹包使揹包中物品的總價值最大且揹包中物品的總重量不超過揹包的容量。

例題代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
const int maxn = 1e4 + 5;
const int maxW = 1e7 + 5;
int n, W, w[maxn], v[maxn];
long long f[maxW];

int main() {
  cin >> W >> n;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
  for (int i = 1; i <= n; i++)
    for (int l = w[i]; l <= W; l++)
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];  // 核心状态方程
  cout << f[W];
  return 0;
}

多重揹包

多重揹包也是 0-1 揹包的一個變式。與 0-1 揹包的區別在於每種物品有 \(k_i\) 個，而非一個。

一個很樸素的想法就是：把「每種物品選 \(k_i\) 次」等價轉換為「有 \(k_i\) 個相同的物品，每個物品選一次」。這樣就轉換成了一個 0-1 揹包模型，套用上文所述的方法就可已解決。狀態轉移方程如下：

\[ f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+v_i\times k) \]

時間複雜度 \(O(W\sum_{i=1}^nk_i)\)。

二進制分組優化

考慮優化。我們仍考慮把多重揹包轉化成 0-1 揹包模型來求解。

解釋

顯然，複雜度中的 \(O(nW)\) 部分無法再優化了，我們只能從 \(O(\sum k_i)\) 處入手。為了表述方便，我們用 \(A_{i,j}\) 代表第 \(i\) 種物品拆分出的第 \(j\) 個物品。

在樸素的做法中，\(\forall j\le k_i\)，\(A_{i,j}\) 均表示相同物品。那麼我們效率低的原因主要在於我們進行了大量重複性的工作。舉例來説，我們考慮了「同時選 \(A_{i,1},A_{i,2}\)」與「同時選 \(A_{i,2},A_{i,3}\)」這兩個完全等效的情況。這樣的重複性工作我們進行了許多次。那麼優化拆分方式就成為了解決問題的突破口。

過程

我們可以通過「二進制分組」的方式使拆分方式更加優美。

具體地説就是令 \(A_{i,j}\left(j\in\left[0,\lfloor \log_2(k_i+1)\rfloor-1\right]\right)\) 分別表示由 \(2^{j}\) 個單個物品「捆綁」而成的大物品。特殊地，若 \(k_i+1\) 不是 \(2\) 的整數次冪，則需要在最後添加一個由 \(k_i-2^{\lfloor \log_2(k_i+1)\rfloor-1}\) 個單個物品「捆綁」而成的大物品用於補足。

舉幾個例子：

  • \(6=1+2+3\)
  • \(8=1+2+4+1\)
  • \(18=1+2+4+8+3\)
  • \(31=1+2+4+8+16\)

顯然，通過上述拆分方式，可以表示任意 \(\le k_i\) 個物品的等效選擇方式。將每種物品按照上述方式拆分後，使用 0-1 揹包的方法解決即可。

時間複雜度 \(O(W\sum_{i=1}^n\log_2k_i)\)

實現

二進制分組代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
index = 0;
for (int i = 1; i <= m; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
index = 0
for i in range(1, m + 1):
    c = 1
    p, h, k = map(int, input().split())
    while k > c:
        k -= c
        index += 1
        list[index].w = c * p
        list[index].v = c * h
        c *= 2
    index += 1
    list[index].w = p * k
    list[index].v = h * k

單調隊列優化

見 單調隊列/單調棧優化。

習題：「Luogu P1776」寶物篩選_NOI 導刊 2010 提高（02）

混合揹包

混合揹包就是將前面三種的揹包問題混合起來，有的只能取一次，有的能取無限次，有的只能取 \(k\) 次。

這種題目看起來很嚇人，可是隻要領悟了前面幾種揹包的中心思想，並將其合併在一起就可以了。下面給出偽代碼：

過程

1
2
3
4
5
6
7
8
for (循環物品種類) {
  if (是 0 - 1 揹包)
    套用 0 - 1 揹包代碼;
  else if (是完全揹包)
    套用完全揹包代碼;
  else if (是多重揹包)
    套用多重揹包代碼;
}
「Luogu P1833」櫻花

題意概要：有 \(n\) 種櫻花樹和長度為 \(T\) 的時間，有的櫻花樹只能看一遍，有的櫻花樹最多看 \(A_{i}\) 遍，有的櫻花樹可以看無數遍。每棵櫻花樹都有一個美學值 \(C_{i}\)，求在 \(T\) 的時間內看哪些櫻花樹能使美學值最高。

二維費用揹包

「Luogu P1855」榨取 kkksc03

有 \(n\) 個任務需要完成，完成第 \(i\) 個任務需要花費 \(t_i\) 分鐘，產生 \(c_i\) 元的開支。

現在有 \(T\) 分鐘時間，\(W\) 元錢來處理這些任務，求最多能完成多少任務。

這道題是很明顯的 0-1 揹包問題，可是不同的是選一個物品會消耗兩種價值（經費、時間），只需在狀態中增加一維存放第二種價值即可。

這時候就要注意，再開一維存放物品編號就不合適了，因為容易 MLE。

實現

1
2
3
4
for (int k = 1; k <= n; k++)
  for (int i = m; i >= mi; i--)    // 對經費進行一層枚舉
    for (int j = t; j >= ti; j--)  // 對時間進行一層枚舉
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);

1
2
3
4
for k in range(1, n + 1):
    for i in range(m, mi - 1, -1): # 對經費進行一層枚舉
        for j in range(t, ti - 1, -1): # 對時間進行一層枚舉
            dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1)

分組揹包

「Luogu P1757」通天之分組揹包

有 \(n\) 件物品和一個大小為 \(m\) 的揹包，第 \(i\) 個物品的價值為 \(w_i\)，體積為 \(v_i\)。同時，每個物品屬於一個組，同組內最多隻能選擇一個物品。求揹包能裝載物品的最大總價值。

這種題怎麼想呢？其實是從「在所有物品中選擇一件」變成了「從當前組中選擇一件」，於是就對每一組進行一次 0-1 揹包就可以了。

再説一説如何進行存儲。我們可以將 \(t_{k,i}\) 表示第 \(k\) 組的第 \(i\) 件物品的編號是多少，再用 \(\mathit{cnt}_k\) 表示第 \(k\) 組物品有多少個。

實現

1
2
3
4
5
6
for (int k = 1; k <= ts; k++)          // 循環每一組
  for (int i = m; i >= 0; i--)         // 循環揹包容量
    for (int j = 1; j <= cnt[k]; j++)  // 循環該組的每一個物品
      if (i >= w[t[k][j]])             // 揹包容量充足
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1揹包一樣狀態轉移

1
2
3
4
5
for k in range(1, ts + 1): # 循環每一組
    for i in range(m, -1, -1): # 循環揹包容量
        for j in range(1, cnt[k] + 1):     # 循環該組的每一個物品
            if i >= w[t[k][j]]: #揹包容量充足
                dp[i] = max(dp[i], dp[i - w[t[k][j]]] + c[t[k][j]]) # 像0-1揹包一樣狀態轉移

這裏要注意：一定不能搞錯循環順序，這樣才能保證正確性。

有依賴的揹包

「Luogu P1064」金明的預算方案

金明有 \(n\) 元錢，想要買 \(m\) 個物品，第 \(i\) 件物品的價格為 \(v_i\)，重要度為 \(p_i\)。有些物品是從屬於某個主件物品的附件，要買這個物品，必須購買它的主件。

目標是讓所有購買的物品的 \(v_i \times p_i\) 之和最大。

考慮分類討論。對於一個主件和它的若干附件，有以下幾種可能：只買主件，買主件 + 某些附件。因為這幾種可能性只能選一種，所以可以將這看成分組揹包。

如果是多叉樹的集合，則要先算子節點的集合，最後算父節點的集合。

泛化物品的揹包

這種揹包，沒有固定的費用和價值，它的價值是隨着分配給它的費用而定。在揹包容量為 \(V\) 的揹包問題中，當分配給它的費用為 \(v_i\) 時，能得到的價值就是 \(h\left(v_i\right)\)。這時，將固定的價值換成函數的引用即可。

雜項

小優化

根據貪心原理，當費用相同時，只需保留價值最高的；當價值一定時，只需保留費用最低的；當有兩件物品 \(i,j\) 且 \(i\) 的價值大於 \(j\) 的價值並且 \(i\) 的費用小於 \(j\) 的費用時，只需保留 \(i\)。

揹包問題變種

實現

輸出方案其實就是記錄下來揹包中的某一個狀態是怎麼推出來的。我們可以用 \(g_{i,v}\) 表示第 \(i\) 件物品佔用空間為 \(v\) 的時候是否選擇了此物品。然後在轉移時記錄是選用了哪一種策略（選或不選）。輸出時的偽代碼：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int v = V;  // 記錄當前的存儲空間

// 因為最後一件物品存儲的是最終狀態，所以從最後一件物品進行循環
for (從最後一件循環至第一件) {
  if (g[i][v]) {
    選了第 i 項物品;
    v -= 第 i 項物品的重量;
  } else {
    未選第 i 項物品;
  }
}

求方案數

對於給定的一個揹包容量、物品費用、其他關係等的問題，求裝到一定容量的方案總數。

這種問題就是把求最大值換成求和即可。

例如 0-1 揹包問題的轉移方程就變成了：

\[ \mathit{dp}_i=\sum(\mathit{dp}_i,\mathit{dp}_{i-c_i}) \]

初始條件：\(\mathit{dp}_0=1\)

因為當容量為 \(0\) 時也有一個方案，即什麼都不裝。

求最優方案總數

要求最優方案總數，我們要對 0-1 揹包裏的 \(\mathit{dp}\) 數組的定義稍作修改，DP 狀態 \(f_{i,j}\) 為在只能放前 \(i\) 個物品的情況下，容量為 \(j\) 的揹包「正好裝滿」所能達到的最大總價值。

這樣修改之後，每一種 DP 狀態都可以用一個 \(g_{i,j}\) 來表示方案數。

\(f_{i,j}\) 表示只考慮前 \(i\) 個物品時揹包體積「正好」是 \(j\) 時的最大價值。

\(g_{i,j}\) 表示只考慮前 \(i\) 個物品時揹包體積「正好」是 \(j\) 時的方案數。

轉移方程：

如果 \(f_{i,j} = f_{i-1,j}\) 且 \(f_{i,j} \neq f_{i-1,j-v}+w\) 説明我們此時不選擇把物品放入揹包更優，方案數由 \(g_{i-1,j}\) 轉移過來，

如果 \(f_{i,j} \neq f_{i-1,j}\) 且 \(f_{i,j} = f_{i-1,j-v}+w\) 説明我們此時選擇把物品放入揹包更優，方案數由 \(g_{i-1,j-v}\) 轉移過來，

如果 \(f_{i,j} = f_{i-1,j}\) 且 \(f_{i,j} = f_{i-1,j-v}+w\) 説明放入或不放入都能取得最優解，方案數由 \(g_{i-1,j}\) 和 \(g_{i-1,j-v}\) 轉移過來。

初始條件：

1
2
3
memset(f, 0x3f3f, sizeof(f));  // 避免沒有裝滿而進行了轉移
f[0] = 0;
g[0] = 1;  // 什麼都不裝是一種方案

因為揹包體積最大值有可能裝不滿，所以最優解不一定是 \(f_{m}\)。

最後我們通過找到最優解的價值，把 \(g_{j}\) 數組裏取到最優解的所有方案數相加即可。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
for (int i = 0; i < N; i++) {
  for (int j = V; j >= v[i]; j--) {
    int tmp = std::max(dp[j], dp[j - v[i]] + w[i]);
    int c = 0;
    if (tmp == dp[j]) c += cnt[j];                       // 如果從dp[j]轉移
    if (tmp == dp[j - v[i]] + w[i]) c += cnt[j - v[i]];  // 如果從dp[j-v[i]]轉移
    dp[j] = tmp;
    cnt[j] = c;
  }
}
int max = 0;  // 尋找最優解
for (int i = 0; i <= V; i++) {
  max = std::max(max, dp[i]);
}
int res = 0;
for (int i = 0; i <= V; i++) {
  if (dp[i] == max) {
    res += cnt[i];  // 求和最優解方案數
  }
}

揹包的第 k 優解

普通的 0-1 揹包是要求最優解，在普通的揹包 DP 方法上稍作改動，增加一維用於記錄當前狀態下的前 k 優解，即可得到求 0-1 揹包第 \(k\) 優解的算法。 具體來講：\(\mathit{dp_{i,j,k}}\) 記錄了前 \(i\) 個物品中，選擇的物品總體積為 \(j\) 時，能夠得到的第 \(k\) 大的價值和。這個狀態可以理解為將普通 0-1 揹包只用記錄一個數據的 \(\mathit{dp_{i,j}}\) 擴展為記錄一個有序的優解序列。轉移時，普通揹包最優解的求法是 \(\mathit{dp_{i,j}}=\max(\mathit{dp_{i-1,j}},\mathit{dp_{i-1,j-v_{i}}}+w_{i})\)，現在我們則是要合併 \(\mathit{dp_{i-1,j}}\)，\(\mathit{dp_{i-1,j-v_{i}}}+w_{i}\) 這兩個大小為 \(k\) 的遞減序列，並保留合併後前 \(k\) 大的價值記在 \(\mathit{dp_{i,j}}\) 裏，這一步利用雙指針法，複雜度是 \(O(k)\) 的，整體時間複雜度為 \(O(nmk)\)。空間上，此方法與普通揹包一樣可以壓縮掉第一維，複雜度是 \(O(mk)\) 的。

例題 HDU 2639 Bone Collector II

求 0-1 揹包的嚴格第 \(k\) 優解。\(n \leq 100,v \leq 1000,k \leq 30\)

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
memset(dp, 0, sizeof(dp));
int i, j, p, x, y, z;
scanf("%d%d%d", &n, &m, &K);
for (i = 0; i < n; i++) scanf("%d", &w[i]);
for (i = 0; i < n; i++) scanf("%d", &c[i]);
for (i = 0; i < n; i++) {
  for (j = m; j >= c[i]; j--) {
    for (p = 1; p <= K; p++) {
      a[p] = dp[j - c[i]][p] + w[i];
      b[p] = dp[j][p];
    }
    a[p] = b[p] = -1;
    x = y = z = 1;
    while (z <= K && (a[x] != -1 || b[y] != -1)) {
      if (a[x] > b[y])
        dp[j][z] = a[x++];
      else
        dp[j][z] = b[y++];
      if (dp[j][z] != dp[j][z - 1]) z++;
    }
  }
}
printf("%d\n", dp[m][K]);

參考資料與註釋

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：hydingsy, Link-cute, Ir1d, greyqz, LuoshuiTianyi, Odeinjul, xyf007, GoodCoder666, paigeman, shenshuaijie
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用