99青青青,97资源久久,婷婷五月天亚洲人妻

背包問題算是動態(tài)規(guī)劃里的基礎(chǔ)問題了，但是并不是背包問題就很簡單。徹底明白其中的原理，是我們理解動態(tài)規(guī)劃算法的基礎(chǔ)，下面的總結(jié)基本來至《背包問題九講》。總結(jié)的過程總是能促進我們自己的思考，希望每個努力提高自己的小伙伴兒都能攻下心中的堡壘。

1. 01背包問題

題目
有 $N$ 件物品和一個容量為 $V$ 的背包。放入第 $i$ 件物品耗費的費用是 $C_i$ (也即占用背包的容量)，得到的價值是 $W_i$ 。求解將哪些物品裝入背包可使價值總和最大。

分析求解
首先定義狀態(tài)： $F[i, v]$ 表示前 $i$ 件物品放入容量為 $v$ 的背包能得到的最大價值。

當(dāng)我們考察第 $i$ 件物品的時候，前 $i-1$ 件物品已經(jīng)確認(rèn)，我們此時只需要考慮對第 $i$ 件物品進行操作：裝入背包或者不裝入背包。
當(dāng)我們選擇不裝入背包時，則有 $F[i,v] = F[i-1, v]$ ，即前 $i-1$ 件物品裝入背包中的最大價值為 $v$ ；當(dāng)我們選擇裝入背包時，則有 $F[i, v] = F[i-1, v-C_i] + W_i$ ，因為我們此時裝入了第 $i$ 件物品，它耗費的費用為 $C_i$ ，所以沒有裝入前背包容量為 $v-C_i$ 。

因為 $F[i, v]$ 表示的是前 $i$ 件物品放入容量為 $v$ 的背包能得到的最大價值，所以我們需要計算裝與不裝兩種情況下的最大值，即
$F[i, v] = max(F[i-1, v], F[i-1, v-C_i]+W_i)$

這便是我們的狀態(tài)轉(zhuǎn)移方程。
偽代碼如下：

F[0,…,V] = 0
for i in 1 to N:
    for v in Ci to V:
        F[i, v] = max(F[i-1, v], F[i-1, v-Ci] + Wi)

狀態(tài)壓縮
接下來考慮對狀態(tài)進行壓縮。由上面的狀態(tài)轉(zhuǎn)移方程，當(dāng)我們計算 $F[i, v]$ 時，需要取用 $F[i-1,v]$ 和 $F[i-1,v-Ci]$ 的值。如果我們只用一個一維數(shù)組 $F[v]$ 來存儲這個值是否能滿足要求呢？
我們需要保證更新 $F[v]$ 時， $F[v-Ci]$ 保存的是 $F[i-1, v-Ci]$ 的值，所以我們可以在內(nèi)循環(huán)中由大到小的順序來更新：

F[0,…,V] = 0
for i in 1 to N:
    for v in V to Ci:
        F[v] = max(F[v], F[v-Ci] + Wi)

我們再內(nèi)循環(huán)抽象成函數(shù)，寫成如下形式：

def ZeroOnePack(F, C, W):
    for v in V to C:
        F[v] = max(F[v], F[v-C]+W)

F[0,…,V] = 0
for i in 1 to N:
    ZeroOnePack(F, Ci, Wi)

復(fù)雜度
時間復(fù)雜度： $O(VN)$ ，即兩重循環(huán)。
空間復(fù)雜度： $O(V)$ ，即 $F$ 占用的空間

初始化
對于 $F$ 的初始化問題，需要考慮題目要求，若是說需要裝滿背包，則除了 $F[0]=0$ 外，其他的需要定義為 $-inf$ ，因為初始時背包中未裝物品，都為非法狀態(tài)；如沒有說要裝滿背包，則全部定義為 $0$ 。

2. 完全背包問題

題目
有 $N$ 種物品和一個容量為 $V$ 的背包，每種物品都有無限件。放入第 $i$ 件物品耗費的費用是 $C_i$ (也即占用背包的容量)，得到的價值是 $W_i$ 。求解將哪些物品裝入背包可使價值總和最大。

分析求解
此問題和 01背包問題非常相似，不同的是物品有無限件，現(xiàn)在就不是選與不選的問題，而是選取多少件(0件、1件、…、 $V/C_i$ 件)的問題。我們?nèi)匀挥?1背包問題的思路來求解：
$F[i, v] = max(F[i-1, v], F[i-1, v-kC_i]+kW_i|0\leqslant kC_i \leqslant v)$
此時我們需要求解的狀態(tài)數(shù)仍然是 $O(VN)$ ，但是求解每一個狀態(tài)的時間復(fù)雜度不再是 $O(1)$ ，而是 $O(v/C_i)$ ，總的時間復(fù)雜度為 $O(VN\sum\frac{V}{C_i})$ 。

此外，我們也可以將每種物品看做 $V/C_i$ 件價值和費用都相同的物品，然后完全套用01背包問題進行求解。更加高效的方式是將第 $i$ 種物品拆分成費用為 $C_i2^k$ 、價值為 $W_i2^k$ 的物品，其中 $k$ 為滿足 $C_i2^k\leqslant V$ 的非負(fù)整數(shù)。

再進一步：在01背包問題中，我們的狀態(tài)轉(zhuǎn)移方程為
$F[i, v] = max(F[i-1, v], F[i-1, v-C_i]+W_i)$
即我們考察第 $i$ 件物品的時候，依據(jù)的是前 $i-1$ 件裝選背包的狀態(tài)。而此時我們第 $i$ 種物品有無限件，當(dāng)我們考察第 $i$ 種物品的時候，就有可能是“加選一件第 $i$ 種物品”，于是這里就存在 “加選” 與 “不加選” 這兩種情形，所以此時我們的狀態(tài)轉(zhuǎn)移方程為
$F[i, v] = max(F[i, v], F[i, v-C_i]+W_i)$
同樣對狀態(tài)進行壓縮：
$F[v] = max(F[v], F[v-Ci] + Wi)$
需要注意的是，此時的 $F[v-C_i]$ 保存的是 $F[i, v-C_i]$ 的值，所以我們的內(nèi)循環(huán)要采用遞增的方式：

F[0,…,V] = 0
for i in 1 to N:
    for v in Ci to V:
        F[v] = max(F[v], F[v-Ci] + Wi)

我們再將內(nèi)循環(huán)抽象成函數(shù)，寫成如下形式：

def CompletePack(F, C, W):
    for v in C to V:
        F[v] = max(F[v], F[v-C]+W)

F[0,…,V] = 0
for i in 1 to N:
    CompletePack(F, Ci, Wi)

3. 多重背包問題

題目
有 $N$ 種物品和一個容量為 $V$ 的背包，第 $i$ 種物品最多有 $M_i$ 件物品可用。放入第 $i$ 件物品耗費的費用是 $C_i$ (也即占用背包的容量)，得到的價值是 $W_i$ 。求解將哪些物品裝入背包可使價值總和最大。

分析求解
對比完全背包問題，多重背包問題每種物品的件數(shù)有限制，當(dāng)用01背包問題求解思路時，狀態(tài)轉(zhuǎn)移方程可寫成
$F[i, v] = max(F[i-1, v], F[i-1, v-kC_i]+kW_i|0\leqslant k \leqslant M_i)$
因為求解每個狀態(tài)的時間復(fù)雜度為 $O(M_i)$ ，所以總的時間復(fù)雜度為 $O(VN \sum M_i)$ 。

和完全背包問題類似，我們還可以考慮將每種物品看做 $M_i$ 件費用和價值都相等的物品來應(yīng)用01背包問題的求解方法；此外，利用二進制的思想，同樣可以將第 $i$ 種物品拆分成系數(shù)為 $1, 2, 2^2, \cdots, 2^{k-1}, M_i-2^k+1$ 的幾件物品，其中 $k$ 是滿足 $M_i-2^k+1>0$ 的最大整數(shù)。

這就將第 $i$ 種物品分成了 $O(logM_i)$ 種物品，也將原問題的復(fù)雜度轉(zhuǎn)化成了 $O(VN\,logM_i)$ 。

def MultiplePack(F, C, W, M):
    if C*M >= V:
        CompletePack(F, C, W)
        return
    k = 1
    while k < M:
        ZeroOnePack(F, k*C, k*W)
        M = M - k
        k = 2 * k
    ZeroOnePack(F, M*C, M*W)

若題目的問題是”這些若干件的物品能否填滿給定容量的背包“，這里只考慮背包容量，而不考慮物品價值，那還能得到時間復(fù)雜度為 $O(VN)$ 的算法。
我們將狀態(tài) $F[i, j]$ 定義為用前 $i$ 件物品填滿容量為 $j$ 的背包后還剩下幾個第 $i$ 種物品可用，如果 $F[i, j]=-1$ ，則表明狀態(tài)不可用，若可行應(yīng)滿足 $0\leqslant F[i, j] \leqslant Mi$ 。

F[0,…,V] = -1
F[0,0] =  0
for i in 1 to N:
    for j in 0 to V:
        if F[i-1, j] >= 0:
            F[i, j] = Mi
        else:
            F[i, j] = -1
    for j in 0 to V-Ci:
        if F[i, j] > 0:
            F[i, j+Ci] = max(F[i, j+Ci], F[i][j]-1)

4. 混合3種背包問題

我們只需要在對每件物品考察前，判斷其數(shù)量，然后分別處理即可。

F[0,…,V] = 0
for i in 1 to N:
    if 第 i 件物品屬于 01 背包:
        ZeroOnePack(F, Ci, Wi)
    elif 第 i 件物品屬于 完全背包:
        CompletePack(F, Ci, Wi)
    elif 第 i 件物品屬于 多重背包:
        MultiplePack(F, Ci, Wi, Mi)

5. 二維費用的背包問題

題目
與前面背包問題不同的是，二維費用主要是指每種物品有兩種不同的費用(背包容量)。
定義第 $i$ 種物品所需的兩種費用為 $C_i$ 和 $D_i$ ，兩種費用可付出的最大值(背包容量) 分別為 $V$ 和 $U$ ，物品的價值為 $W_i$ 。

分析求解
我們只需要在前述基礎(chǔ)上，將狀態(tài)增加一維即可。設(shè) $F[i, v, u]$ 為前 $i$ 件物品分別付出費用為 $v$ 和 $u$ 時可獲得的最大價值，則狀態(tài)轉(zhuǎn)移方程為：
$F[i, v, u] = max(F[i, v, u], F[i-1, v-C_i, u-D_i]+W_i)$

同樣可以考慮對狀態(tài)進行壓縮。若是01背包問題，內(nèi)循環(huán)時需要遞減的順序；若是完全背包問題，內(nèi)循環(huán)需要遞增的順序；多重背包問題時，同樣對物品進行拆分處理。

物品總件數(shù)的限制
二維費用問題通常是以一種隱含的方式給出的：最多只能選擇 $U$ 件物品。其實這相當(dāng)于多了一種 "件數(shù)" 的費用，每個物品的件數(shù)費用均為1，可以付出的最大件數(shù)費用的 $U$ ，即 $F[v, u]$ 表示付出費用為 $v$ ，最多選擇 $u$ 件時的最大價值。

6. 分組背包問題

題目
有 $N$ 件物品和一個容量為 $V$ 的背包。放入第 $i$ 件物品耗費的費用是 $C_i$ (也即占用背包的容量)，得到的價值是 $W_i$ 。這些物品被劃分為 $K$ 組，每組中的物品互相沖突，最多只能選一件，求解將哪些物品裝入背包可使價值總和最大。

分析求解
這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。設(shè) $F[k,v]$ 表示前 $k$ 組物品花費費用 $v$ 能取得的最大權(quán)值，則有
$F[k, v] = max(F[k-1, v], F[k-1, v-C_i]+W_i|item\,i\in group\,k)$

同樣可進行空間復(fù)雜度的優(yōu)化，偽代碼如下：

for k in 1 to K:
    for v in V to Ci:
        for all item i in group k:
            F[v] = max(F[v], F[v-Ci]+Wi)

這里三層循環(huán)的順序保證了每一組內(nèi)的物品最多只有一個會被添加到背包中。

7. 有依賴的背包問題

題目
這里的依賴定義為選擇物品 $i$ ，則必須選物品 $j$ ，也稱為物品 $i$ 依賴于物品 $j$ 。我們假設(shè)沒有某個物品既依賴于別的物品，又被別的物品所依賴，另外，沒有某件物品同時依賴多件物品。

分析求解
我們將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。我們考慮一個主件和它的附件集合，選擇策略有：一個都不選、選擇主件和一個附件、選擇主件和2個附件……這樣對于有 $n$ 個附件的集合，那我們的選擇策略有 $2^n+1$ 種。

值得關(guān)注的是，這些策略都是互斥的，我們可以將某個主件和它的附件集合看做一個分組，利用 6 中的分組背包問題求解，但遺憾的是選擇策略并沒有減少，依然是指數(shù)級。

對于第 $k$ 個物品組中的物品，如有費用相同的物品，則可以只保留一個價值最大的物品，這算是一個小優(yōu)化。此外，對于主件 $k$ 的附件集合，我們可以應(yīng)用一次01背包算法，得到費用依次為 $0,…,V-C_k$ 所有這些值時相應(yīng)的最大價值 $F[0, …,V-C_k]$ ，這樣就可以將主件 $k$ 及它的附件集合看做為 $V-C_k+1$ 個物品的物品組，其中費用為 $v$ 的物品的價值為 $F_k[v-C_k]+W_k$ ， $v$ 的取值范圍為 $C_k\leqslant v \leqslant V$ ，接下來再應(yīng)用 6 中的分組背包算法求解。

更一般的情況
更通常的情況是主件的附件依然存在附件，但是一般都會限制每個物品最多只依賴一個物品，且不會出現(xiàn)循環(huán)依賴。
解決這類問題，只能從最底層開始，先將附件轉(zhuǎn)換成物品組，在一層一層向上求解。

8. 泛化物品

泛化物品沒有固定的費用和價值，它的價值隨著分配給它的費用而發(fā)生變化。
在背包容量為 $V$ 的背包問題中，泛化物品是一個定義域為 $0,…,V$ 中整數(shù)的函數(shù) $h$ ，當(dāng)分配給它的費用為 $v$ 時，能得到的價值就是 $h(v)$ 。

一個費用為 $c$ ，價值為 $w$ 的物品，若它是01背包中的物品，則可以看做是 $h(c)=w$ ，其余函數(shù)值都為 $0$ 的泛化物品；若是完全背包問題，則其價值函數(shù)為 $h(c) = w * (v/c)$ ，除 $v/c$ 為整數(shù)值外，其余值都為 $0$ ；若是件數(shù)為 $m$ 的多重背包問題，則 $h(c)=w*(v/c)$ ，當(dāng)且僅當(dāng) $v/c$ 為整數(shù)且 $v/c \leqslant m$ 時有價值，其余情況均為 $0$ 。

一個物品組可以看做一個泛化物品 $h$ ，對于一個 $0,…,V$ 中的 $v$ ，若物品組不存在費用為 $v$ 的物品，則 $h(v)=0$ ，否則 $h(v)$ 取值為所有費用為 $v$ 的物品的最大價值。對于 7 中的每個主件和其附件集合，就可以看做是一個泛化物品。

泛化物品的和
若給定了兩個泛化物品 $h$ 和 $l$ ，給定費用為 $v$ 的情況求其最大價值，則我們只需要枚舉將這個費用如何分配給兩個物品即可。對于 $0,…,V$ 中的每一個整數(shù) $v$ ，最大價值 $f(v)$ 即為：
$f(v) = max(h(k) + l(v-k)|0 \leqslant k \leqslant v)$
這樣看來， $f$ 也可以看做是 $h$ 和 $l$ 決定的泛化物品， $f$ 定義為泛化物品 $h$ 和 $l$ 的和。所以我們的背包問題，也都可以看做是泛化物品的求和問題。

9. 背包問題問法的變化

一般的背包問題，都是在限制容量的情況下求解最大價值，類似的問題還有最多可以裝多少件物品，最多可以裝滿多少空間的背包等，這類問題都可以根據(jù)最終的狀態(tài)數(shù)組 $F$ 求得。對于“最小價值” 和 "最少件數(shù)" 的問題，則只需要將狀態(tài)轉(zhuǎn)移方程中的 max 改成 min 即可。下面總結(jié)下其他變相問法。

輸出方案
問題需要我們給出最終選擇的物品集合。對于這類問題，我們在求解過程中需要記錄狀態(tài)轉(zhuǎn)移的過程，即每個狀態(tài)的最優(yōu)值是由狀態(tài)轉(zhuǎn)移方程的哪一項推出來的。

以01背包問題為例，狀態(tài)轉(zhuǎn)移方程為 $F[i, v] = max(F[i-1, v], F[i-1, v-C_i]+W_i)$ ，我們定義一個數(shù)組 $G[i, v]$ ， $G[i, v]=0$ 表示推出 $F[i,v]$ 的值時采用了方程的前一項( $F[i-1, v]$ )， $G[i, v]=1$ 表示推出 $F[i,v]$ 的值時采用了方程的后一項( $F[i-1, v-C_i]+W_i$ )，則最后輸出方案為：

i = N
v = V
while i > 0:
    if G[i, v] == 0:
        print(未選擇第 i 件物品)
    if G[i, v] == 1:
        print(選擇第 i 件物品)
        v = v - Ci
    i = i - 1

當(dāng)然我們也可以不采用 $G[i,v]$ ，而是利用 $F[i, v]$ 進行推算：將 $G[i,v]==0$ 改為 $F[i,v] == F[i-1, v]$ ，將 $G[i,v]==1$ 改為 $F[i,v] == F[i-1, v-C_i]+W_i$ 即可。

求方案總數(shù)
由于狀態(tài)轉(zhuǎn)移方程考慮了所有可能的背包組成方案，所以我們只需要將狀態(tài)轉(zhuǎn)移方程中的 max 改成 sum 即可。

求最優(yōu)方案總數(shù)
以01背包問題為例，我們定義一個數(shù)組 $G[i,v]$ 來同步求解最優(yōu)方案的總數(shù)

G[0, 0] = 1
for i in 1 to N:
    for v in 0 to V:
        F[i, v] = max(F[i-1, v], F[i-1, v-Ci]+Wi)
        if F[i, v] == F[i-1, v]:
            G[i, v] = G[i, v] + G[i-1, v]
        if F[i, v] == F[i-1, v-Ci]+Wi
            G[i, v] = G[i, v] + G[i-1, v-Ci]

求次優(yōu)解、第K優(yōu)解
以01背包問題、求解第 $K$ 優(yōu)解為例進行說明。要點在于將每個狀態(tài)都表示成有序隊列，狀態(tài)轉(zhuǎn)移方程中的 max 改成有序隊列的合并。

對于01背包問題的狀態(tài)轉(zhuǎn)移方程 $F[i, v] = max(F[i-1, v], F[i-1, v-C_i]+W_i)$ ，我們需要求解第 $K$ 優(yōu)解，則狀態(tài) $F[i,v]$ 就為一個大小為 $K$ 的隊列 $F[i,v,1…K]$ ， $F[i, v, k]$ 就表示前 $i$ 個物品中，背包大小為 $v$ 時，第 $k$ 優(yōu)解的值。當(dāng)進行合并時，我們只需要將 $F[i-1, v, 1…K]$ 和 $F[i-1,v-C_i, 1…K]+W_i$ 的前 $k$ 大值存入到 $F[i, v, 1…K]$ 中即可，總的時間復(fù)雜度為 $O(VNK)$ 。