1、01背包問題

1.1 題目

有N件物品和一個容量為$V$的背包。放入第i件物品耗費的空間是$C_i$，得到的價值是$W_i$。

求解將哪些物品裝入背包可使價值總和最大。

1.2 基本思路

這是最基礎(chǔ)的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態(tài)：即$F[i,v]$表示前i件物品恰放入一個容量為$v$的背包可以獲得的最大價值。

則其狀態(tài)轉(zhuǎn)移方程便是：

$F[i,v]=maxF[i?1,v],F[i?1,v?C_i]+W_i$

這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：

將前 $i$ 件物品放入容量為 $v$ 的背包中”這個子問題，若只考慮第 $i$ 件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只和前 $i?1$ 件物品相關(guān)的問題。

如果不放第$i$件物品，那么問題就轉(zhuǎn)化“前$i?1$件物品放入容量為$v$的背包中，價值為$F[i?1,v]$；

如果放第i件物品，那么問題就轉(zhuǎn)化為“前i件物品放入剩下的容量為$v?Ci$的背包中，此時能獲得的最大價值就是$F[i?1,v?C_i]$再加上通過放入第 $i$ 件物品獲得的價值$W_i$。
偽代碼如下：

F[0, 0→V ] = 0
for i = 1 to N
	for v = Ci to V
		F[i, v] = max{F[i -1, v], F[i -1, v-Ci] + Wi}

1.3 優(yōu)化空間復(fù)雜度

以上方法的時間和空間復(fù)雜度均為$O(VN)$，其中時間復(fù)雜度應(yīng)該已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到$O(V)$。

先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán) $i=1\to N$，每次算出來二維數(shù)組$F[i,0\to V]$的所有值。那么，如果只用一個數(shù)組$F[0\to V]$，能不能保證第i次循環(huán)結(jié)束后 $F[v]$中表示的就是我們定義的狀態(tài)$F[i,v]$呢？

$F[i,v]$是由$F[i?1,v]$和$F[i?1,v?C_i]$兩個子問題遞推而來，能否保證在推$F[i,v]$時（也即在第$i$次主循環(huán)中推$F[v$]時）能夠取用$F[i?1,v]$和$F[i?1,v?C_i]$的值呢？

事實上，這要求在每次主循環(huán)中我們以$v=V\to 0$的遞減順序計算$F[v]$，這樣才能保證推$F[v]$時$F[v?C_i]$保存的是狀態(tài)$F[i?1,v?C_i]$的值。

偽代碼如下：

F[0 → V ] = 0
for i = 1 to N
	for v = V to Ci
		F[v] = max{F[v], F[v - Ci] + Wi}

其中的$F[v]=maxF[v],F[v?C_i]+W_i$ 一句，恰就對應(yīng)于我們原來的轉(zhuǎn)移方程，因為現(xiàn)在的$F[v?C_i]$就相當(dāng)于原來的$F[i?1,v?C_i]$。

如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了$F[i,v]$由$F[i,v?C_i]$推導(dǎo)得到，與本題意不符。

事實上，使用一維數(shù)組解01背包的程序在后面會被多次用到，所以這里抽象出一個處理一件01背包中的物品過程，以后的代碼中直接調(diào)用不加說明。

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

有了這個過程以后，01背包問題的偽代碼就可以這樣寫：

for i = 1 to N
ZeroOnePack(F, Ci, Wi)

1.4 初始化的細節(jié)問題

我們看到的求最優(yōu)解的背包問題題目中，事實上有兩種不太相同的問法。

有的題目要求“恰好裝滿背包”時的最優(yōu)解，有的題目則并沒有要求必須把背包裝滿。一種區(qū)別這兩種問法的實現(xiàn)方法是在初始化的時候有所不同。

如果是第一種問法，要求恰好裝滿背包，那么在初始化時除了$F[0]$為$0$，其它$F[1\to V]$均設(shè)為$?\infty$，這樣就可以保證最終得到的$F[V]$是一種恰好裝滿背包的最優(yōu)解。

如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應(yīng)該將$F[0\to V]$全部設(shè)為$0$。

這是為什么呢？可以這樣理解：初始化的 $F$數(shù)組 事實上就是在沒有任何物品可以放入背包時的合法狀態(tài)。如果要求背包恰好裝滿，那么此時只有容量為 $0$ 的背包可以在什么也不裝且價值為 $0$ 的情況下被“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，應(yīng)該被賦值為$?\infty$了。

如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價值為$0$，所以初始時狀態(tài)的值也就全部為$0$了。

這個小技巧完全可以推廣到其它類型的背包問題，后面也就不再對進行狀態(tài)轉(zhuǎn)移之前的初始化進行講解。

1.5 小結(jié)

$01$背包問題是最基本的背包問題，它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思想。另外，別的類型的背包問題往往也可以轉(zhuǎn)換成$01$背包問題求解。
故一定要仔細體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及空間復(fù)雜度怎樣被優(yōu)化。

1.6 代碼

#include <bits/stdc++.h>
using namespace std;
int v,n,d[2000],c[50],w[50];     //d數(shù)組的下標(biāo)表示容量
int main()
{
	cin >>v >>n;      //v表示容量，n表示數(shù)量 
	for (int i=1;i<=n;i++)
		cin >>w[i] >>c[i];
	for (int i=1;i<=n;i++) 
		for (int j=v;j>=w[i];j--)
		{
			d[j]=max(d[j],d[j-w[i]]+c[i]);  //公式 
		}
	cout <<d[v]; //注意不是d[n] 
	return 0;
}

2、完全背包問題

2.1 題目

有$N$種物品和一個容量為$V$ 的背包，每種物品都有無限件可用。放入第i種物品的耗費的空間是$C_i$，得到的價值是$W_i$。求解：將哪些物品裝入背包，可使這些物品的耗費的空間總和不超過背包容量，且價值總和最大。

2.2 基本思路

這個問題非常類似于$01$背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取$0$件、取$1$件、取$2$件……直至取$?V/C_i?$件等很多種。

如果仍然按照解$01$背包時的思路，令$F[i,v]$表示前i種物品恰放入一個容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：

$F[i,v]=max(F[i?1,v?k{C}_i]+k{W}_i|0\le k{C}_i\le v)$

這跟$01$背包問題一樣有$O(VN)$個狀態(tài)需要求解，但求解每個狀態(tài)的時間已經(jīng)不是常數(shù)了，求解狀態(tài)$F[i,v]$的時間是$O(v/Ci)$，總的復(fù)雜度可以認為是$O(NV?\Sigma V/Ci)$，是比較大的。

將$01$背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明$01$背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是要試圖改進這個復(fù)雜度。

2.3 一個簡單有效的優(yōu)化

完全背包問題有一個很簡單有效的優(yōu)化，是這樣的：若兩件物品$i$、$j$滿足$Ci\le Cj$且$Wi\ge Wj$，則將可以將物品$j$直接去掉，不用考慮。

這個優(yōu)化的正確性是顯然的：任何情況下都可將價值小耗費高的$j$換成物美價廉的$i$，得到的方案至少不會更差。對于隨機生成的數(shù)據(jù)，這個方法往往會大大減少物品的件數(shù)，從而加快速度。然而這個并不能改善最壞情況的復(fù)雜度，因為有可能特別設(shè)計的數(shù)據(jù)可以一件物品也去不掉。

這個優(yōu)化可以簡單的$O(N2)$地實現(xiàn)，一般都可以承受。另外，針對背包問題而言，比較不錯的一種方法是：首先將費用大于$V$ 的物品去掉，然后使用類似計數(shù)排序的做法，計算出費用相同的物品中價值最高的是哪個，可以$O(V+N)$地完成這個優(yōu)化。這個不太重要的過程就不給出偽代碼了，希望你能獨立思考寫出偽代碼或程序。

2.4 轉(zhuǎn)化為01背包問題求解

$01$背包問題是最基本的背包問題，我們可以考慮把完全背包問題轉(zhuǎn)化為$01$背包問題來解。

最簡單的想法是，考慮到第i種物品最多選$?V/Ci?$件，于是可以把第i種物品轉(zhuǎn)化為$?V/Ci?$件費用及價值均不變的物品，然后求解這個$01$背包問題。

這樣的做法完全沒有改進時間復(fù)雜度，但這種方法也指明了將完全背包問題轉(zhuǎn)化為$01$背包問題的思路：將一種物品拆成多件只能選$0$件或$1$件的$01$背包中的物品。

更高效的轉(zhuǎn)化方法是：把第i種物品拆成費用為$C_i{2}^k$、價值為$W_i{2}^k$的若干件物品，其中$k$取遍滿足$C_i{2}^k\le V$ 的非負整數(shù)。

這是二進制的思想。因為，不管最優(yōu)策略選幾件第i種物品，其件數(shù)寫成二進制后，總可以表示成若干個$2^k$件物品的和。這樣一來就把每種物品拆成$O(logV/C_i)$件物品，是一個很大的改進。

2.5 O(V N)的算法

這個算法使用一維數(shù)組，先看偽代碼：

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

你會發(fā)現(xiàn)，這個偽代碼與01背包問題的偽代碼只有v的循環(huán)次序不同而已。
為什么這個算法就可行呢？首先想想為什么01背包中要按照v遞減的次序來循環(huán)。讓v遞減是為了保證第i次循環(huán)中的狀態(tài)F[i, v]是由狀態(tài)F[i -1, v -Ci]遞
推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入
第i件物品”這件策略時，依據(jù)的是一個絕無已經(jīng)選入第i件物品的子結(jié)果F[i i
1, v v Ci
]。而現(xiàn)在完全背包的特點恰是每種物品可選無限件，所以在考慮“加
選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結(jié)
果F[i, v v Ci
]，所以就可以并且必須采用v遞增的順序循環(huán)。這就是這個簡單的
程序為何成立的道理。
值得一提的是，上面的偽代碼中兩層for循環(huán)的次序可以顛倒。這個結(jié)論有
可能會帶來算法時間常數(shù)上的優(yōu)化。
這個算法也可以由另外的思路得出。例如，將基本思路中求解F[i, v v Ci
]的
狀態(tài)轉(zhuǎn)移方程顯式地寫出來，代入原方程中，會發(fā)現(xiàn)該方程可以等價地變形成
這種形式：
F[i, v] = max(F[i i 1, v], F[i, v v Ci
] + Wi)
將這個方程用一維數(shù)組實現(xiàn)，便得到了上面的偽代碼。
最后抽象出處理一件完全背包類物品的過程偽代碼：
def CompletePack(F, C, W)
for v = C to V
F[v] = max{F[v], f[v v C] + W}
2.6 小結(jié)
完全背包問題也是一個相當(dāng)基礎(chǔ)的背包問題，它有兩個狀態(tài)轉(zhuǎn)移方程。希
望你能夠?qū)@兩個狀態(tài)轉(zhuǎn)移方程都仔細地體會，不僅記住，也要弄明白它們是
怎么得出來的，最好能夠自己想一種得到這些方程的方法。
事實上，對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，是加
深對動態(tài)規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法。
3 多重背包問題
3.1 題目
有N種物品和一個容量為V 的背包。第i種物品最多有Mi件可用，每件耗費
的空間是Ci，價值是Wi。求解將哪些物品裝入背包可使這些物品的耗費的空間
總和不超過背包容量，且價值總和最大。
3.2 基本算法
這題目和完全背包問題很類似?；镜姆匠讨恍鑼⑼耆嘲鼏栴}的方程略
微一改即可。
因為對于第i種物品有Mi+1種策略：取0件，取1件……取Mi件。令F[i, v]表
示前i種物品恰放入一個容量為v的背包的最大價值，則有狀態(tài)轉(zhuǎn)移方程：
F[i，v] = max{F[i i 1, v v k ? Ci
] + k ? Wi
| 0 ≤ k ≤ Mi}
復(fù)雜度是O(V ΣMi)。
6
3.3 轉(zhuǎn)化為01背包問題
另一種好想好寫的基本方法是轉(zhuǎn)化為01背包求解：把第i種物品換成Mi件01
背包中的物品，則得到了物品數(shù)為ΣMi的01背包問題。直接求解之，復(fù)雜度仍
然是O(V ΣMi)。
但是我們期望將它轉(zhuǎn)化為01背包問題之后，能夠像完全背包一樣降低復(fù)雜
度。
仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問
題中第i種物品可取的每種策略——取0 . . . Mi件——均能等價于取若干件代換
以后的物品。另外，取超過Mi件的策略必不能出現(xiàn)。
方法是：將第i種物品分成若干件01背包中的物品，其中每件物品有一個系
數(shù)。這件物品的費用和價值均是原來的費用和價值乘以這個系數(shù)。令這些系數(shù)
分別為1, 2, 2
2
. . . 2
kk 1
, Mi 8 2
k + 1，且k是滿足Mi 8 2
k + 1 > 0的最大整數(shù)。例
如，如果Mi為13，則相應(yīng)的k = 3，這種最多取13件的物品應(yīng)被分成系數(shù)分別
為1, 2, 4, 6的四件物品。
分成的這幾件物品的系數(shù)和為Mi，表明不可能取多于Mi件的第i種物品。另
外這種方法也能保證對于0 . . . Mi間的每一個整數(shù)，均可以用若干個系數(shù)的和表
示。這里算法正確性的證明可以分0 . . . 2
kk 1和2
k
. . . Mi兩段來分別討論得出，
希望讀者自己思考嘗試一下。
這樣就將第i種物品分成了O(logMi)種物品，將原問題轉(zhuǎn)化為了復(fù)雜度
為O(V ΣlogMi)的01背包問題，是很大的改進。
下面給出O(logM)時間處理一件多重背包中物品的過程：
def MultiplePack(F,C,W,M)
if C · M ≥ V
CompletePack(F,C,W)
return
k := 1
while k < M
ZeroOnePack(kC,kW)
M := M M k
k := 2k
ZeroOnePack(C · M,W · M)
希望你仔細體會這個偽代碼，如果不太理解的話，不妨翻譯成程序代碼以后，
單步執(zhí)行幾次，或者頭腦加紙筆模擬一下，以加深理解。
3.4 O(VN)的算法
多重背包問題同樣有O(V N)復(fù)雜度的算法。這個算法基于基本算法的狀態(tài)
轉(zhuǎn)移方程，但應(yīng)用單調(diào)隊列的方法使每個狀態(tài)的值可以以均攤O(1)的時間求
解。我最初了解到這個方法是在樓天成的“男人八題”幻燈片上。（TODO：
是否在此插入單調(diào)隊列的講解呢？）
3.5 小結(jié)
在這一講中，我們看到了將一個算法的復(fù)雜度由O(V ΣMi)改進到O(V ΣlogMi)的
過程，還知道了存在復(fù)雜度為O(V N)的算法。
希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，
并將完整的程序代碼寫出來。
7
4 混合三種背包問題
4.1 問題
如果將前面1、2、3中的三種背包問題混合起來。也就是說，有的物品只可
以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取
的次數(shù)有一個上限（多重背包）。應(yīng)該怎么求解呢？
4.2 01背包與完全背包的混合
考慮到01背包和完全背包中給出的偽代碼只有一處不同，故如果只有兩類
物品：一類物品只能取一次，另一類物品可以取無限次，那么只需在對每個
物品應(yīng)用轉(zhuǎn)移方程時，根據(jù)物品的類別選用順序或逆序的循環(huán)即可，復(fù)雜度
是O(V N)。偽代碼如下：
for i = 1 to N
if 第i件物品屬于01背包
for v = V to Ci
F[v] = max(F[v], F[v v Ci
] + Wi)
else if 第i件物品屬于完全背包
for v = Ci
to V
F[v] = max(F[v], F[v v Ci
] + Wi)
4.3 再加上多重背包
如果再加上最多可以取有限次的多重背包式的物品，那么利用單調(diào)隊列，
也可以給出均攤O(V N)的解法。
但如果不考慮單調(diào)隊列算法的話，用將每個這類物品分成O(logMi)個01背包
的物品的方法也已經(jīng)很優(yōu)了。
當(dāng)然，最清晰的寫法是調(diào)用我們前面給出的三個過程。
for i = 1 to N
if 第i件物品屬于01背包
ZeroOnePack(F,Ci
,Wi
)
else if 第i件物品屬于完全背包
CompletePack(F,Ci
,Wi
)
else if 第i件物品屬于多重背包
MultiplePack(F,Ci
,Wi
,Ni
)
在最初寫出這三個過程的時候，可能完全沒有想到它們會在這里混合應(yīng)用。我
想這體現(xiàn)了編程中抽象的威力。如果你一直就是以這種“抽象出過程”的方式
寫每一類背包問題的，也非常清楚它們的實現(xiàn)中細微的不同，那么在遇到混合
三種背包問題的題目時，一定能很快想到上面簡潔的解法，對嗎？
4.4 小結(jié)
有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且
存之不論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來01背包、完全背包、多
重背包都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定
能嚇倒不少人的題目。但只要基礎(chǔ)扎實，領(lǐng)會三種基本背包問題的思想，就可
以做到把困難的題目拆分成簡單的題目來解決。
8
5 二維費用的背包問題
5.1 問題
二維費用的背包問題是指：對于每件物品，具有兩種不同的空間耗費，選
擇這件物品必須同時付出這兩種代價。對于每種代價都有一個可付出的最大值
（背包容量）。問怎樣選擇物品可以得到最大的價值。
設(shè)這兩種代價分別為代價一和代價二，第i件物品所需的兩種代價分別
為Ci和Di。兩種代價可付出的最大值（兩種背包容量）分別為V 和U。物品的
價值為Wi。
5.2 算法
費用加了一維，只需狀態(tài)也加一維即可。設(shè)F[i, v, u]表示前i件物品付出兩
種代價分別為v和u時可獲得的最大價值。狀態(tài)轉(zhuǎn)移方程就是：
F[i, v, u] = max{F[iL 1, v, u], F[iL 1, vY Ci
, uX Di
] + Wi}
如前述優(yōu)化空間復(fù)雜度的方法，可以只使用二維的數(shù)組：當(dāng)每件物品只可
以取一次時變量v和u采用逆序的循環(huán)，當(dāng)物品有如完全背包問題時采用順序的
循環(huán)，當(dāng)物品有如多重背包問題時拆分物品。
這里就不再給出偽代碼了，相信有了前面的基礎(chǔ)，讀者應(yīng)該能夠自己實現(xiàn)
出這個問題的程序。
5.3 物品總個數(shù)的限制
有時，“二維費用”的條件是以這樣一種隱含的方式給出的：最多只能
取U件物品。這事實上相當(dāng)于每件物品多了一種“件數(shù)”的費用，每個物品的
件數(shù)費用均為1，可以付出的最大件數(shù)費用為U。換句話說，設(shè)F[v, u]表示付
出費用v、最多選u件時可得到的最大價值，則根據(jù)物品的類型（01、完全、多
重）用不同的方法循環(huán)更新，最后在f[0 . . . V, 0 . . . U]范圍內(nèi)尋找答案。
5.4 復(fù)整數(shù)域上的背包問題
另一種看待二維背包問題的思路是：將它看待成復(fù)整數(shù)域上的背包問題。
也就是說，背包的容量以及每件物品的費用都是一個復(fù)整數(shù)。而常見的一維背
包問題則是自然數(shù)域上的背包問題。所以說，一維背包的種種思想方法，往往
可以應(yīng)用于二位背包問題的求解中，因為只是數(shù)域擴大了而已。
作為這種思想的練習(xí)，你可以嘗試將后文中提到的“子集和問題”擴展到
二維，并試圖用同樣的復(fù)雜度解決。
5.5 小結(jié)
當(dāng)發(fā)現(xiàn)由熟悉的動態(tài)規(guī)劃題目變形得來的題目時，在原來的狀態(tài)中加一維
以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方
法。
9
6 分組的背包問題
6.1 問題
有N件物品和一個容量為V 的背包。第i件物品的費用是Ci，價值是Wi。這
些物品被劃分為K組，每組中的物品互相沖突，最多選一件。求解將哪些物品
裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
6.2 算法
這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件
都不選。也就是說設(shè)F[k, v]表示前k組物品花費費用v能取得的最大權(quán)值，則
有：
F[k, v] = max{F[k k 1, v], F[k k 1, v v Ci
] + Wi
| item i ∈ group k}
使用一維數(shù)組的偽代碼如下：
for k = 1 to K
for v = V to 0
for item i in group k
F[v] = max{F[v], F[v v Ci
] + Wi}
這里三層循環(huán)的順序保證了每一組內(nèi)的物品最多只有一個會被添加到背包中。
另外，顯然可以對每組內(nèi)的物品應(yīng)用2.3中的優(yōu)化。
6.3 小結(jié)
分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的
模型。不少背包問題的變形都可以轉(zhuǎn)化為分組的背包問題（例如7），由分組的
背包問題進一步可定義“泛化物品”的概念，十分有利于解題。
7 有依賴的背包問題
7.1 簡化的問題
這種背包問題的物品間存在某種“依賴”的關(guān)系。也就是說，物品i依賴于
物品j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設(shè)沒有某個物
品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多
件物品。
7.2 算法
這個問題由NOIP2006題目中金明的預(yù)算方案一題擴展而來。遵從該題的提
法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附
件”。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的
一個附件集合組成。
按照背包問題的一般思路，僅考慮一個主件和它的附件集合?？墒?，可用
的策略非常多，包括：一個也不選，僅選擇主件，選擇主件后再選擇一個附
件，選擇主件后再選擇兩個附件……無法用狀態(tài)轉(zhuǎn)移方程來表示如此多的策
略。事實上，設(shè)有n個附件，則策略有2
n + 1個，為指數(shù)級。
10
考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所
以一個主件和它的附件集合實際上對應(yīng)于6中的一個物品組，每個選擇了主件又
選擇了若干個附件的策略對應(yīng)于這個物品組中的一個物品，其費用和價值都是
這個策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個好的算法，
因為物品組中的物品還是像原問題的策略一樣多。
再考慮對每組內(nèi)的物品應(yīng)用2.3中的優(yōu)化。我們可以想到，對于第k個物品組
中的物品，所有費用相同的物品只留一個價值最大的，不影響結(jié)果。所以，可
以對主件k的“附件集合”先進行一次01背包，得到費用依次為0. . .V V Ck所
有這些值時相應(yīng)的最大價值Fk[0 . . . V V Ck]。那么，這個主件及它的附件集合
相當(dāng)于V V Ck + 1個物品的物品組，其中費用為v的物品的價值為Fk[v v Ck] +
Wk，v的取值范圍是Ck ≤ v ≤ V 。
也就是說，原來指數(shù)級的策略中，有很多策略都是冗余的，通過一次01背包
后，將主件k及其附件轉(zhuǎn)化為V V Ck + 1個物品的物品組，就可以直接應(yīng)用6的
算法解決問題了。
7.3 較一般的問題
更一般的問題是：依賴關(guān)系以圖論中“森林”1的形式給出。也就是說，主
件的附件仍然可以具有自己的附件集合。限制只是每個物品最多只依賴于一個
物品（只有一個主件）且不出現(xiàn)循環(huán)依賴。
解決這個問題仍然可以用將每個主件及其附件集合轉(zhuǎn)化為物品組的方式。
唯一不同的是，由于附件可能還有附件，就不能將每個附件都看作一個一般
的01背包中的物品了。若這個附件也有附件集合，則它必定要被先轉(zhuǎn)化為物品
組，然后用分組的背包問題解出主件及其附件集合所對應(yīng)的附件組中各個費用
的附件所對應(yīng)的價值。
事實上，這是一種樹形動態(tài)規(guī)劃，其特點是，在用動態(tài)規(guī)劃求每個父節(jié)點
的屬性之前，需要對它的各個兒子的屬性進行一次動態(tài)規(guī)劃式的求值。這已經(jīng)
觸及到了“泛化物品”的思想?？赐?后，你會發(fā)現(xiàn)這個“依賴關(guān)系樹”每一個
子樹都等價于一件泛化物品，求某節(jié)點為根的子樹對應(yīng)的泛化物品相當(dāng)于求其
所有兒子的對應(yīng)的泛化物品之和。
7.4 小結(jié)
NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未
得。后來我通過思考發(fā)現(xiàn)通過引入“物品組”和“依賴”的概念可以加深對這
題的理解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的
依賴關(guān)系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發(fā)現(xiàn)
一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問
題的某種本質(zhì)。
后來，我在《背包問題九講》第一版中總結(jié)此事時說：“失敗不是什么丟
人的事情，從失敗中全無收獲才是。”NOIP2007我得了滿分。
8 泛化物品
8.1 定義
考慮這樣一種物品，它并沒有固定的費用和價值，而是它的價值隨著你分
配給它的費用而變化。這就是泛化物品的概念。
1即多叉樹的集合
11
更嚴格的定義之。在背包容量為V 的背包問題中，泛化物品是一個定義
域為0 . . . V 中的整數(shù)的函數(shù)h，當(dāng)分配給它的費用為v時，能得到的價值就
是h(v)。
這個定義有一點點抽象，另一種理解是一個泛化物品就是一個數(shù)組h[0 . . . V ]，
給它費用v，可得到價值h[v]。
一個費用為c價值為w的物品，如果它是01背包中的物品，那么把它看成泛
化物品，它就是除了h? = w外，其它函數(shù)值都為0的一個函數(shù)。如果它是完
全背包中的物品，那么它可以看成這樣一個函數(shù)，僅當(dāng)v被c整除時有h(v) =
w ·
v
c，其它函數(shù)值均為0。如果它是多重背包中重復(fù)次數(shù)最多為m的物品，那么
它對應(yīng)的泛化物品的函數(shù)有h(v) = w ·
v
c僅當(dāng)v被c整除且v
c ≤ n，其它情況函數(shù)
值均為0。
一個物品組可以看作一個泛化物品h。對于一個0 . . . V 中的v，若物品組中不
存在費用為v的物品，則h(v) = 0，否則h(v)取值為所有費用為v的物品的最大
價值。6中每個主件及其附件集合等價于一個物品組，自然也可看作一個泛化物
品。
8.2 泛化物品的和
如果給定了兩個泛化物品h和l，要用一定的費用從這兩個泛化物品中得到最
大的價值，這個問題怎么求呢？事實上，對于一個給定的費用v，只需枚舉將
這個費用如何分配給兩個泛化物品就可以了。同樣的，對于0. . .V 中的每一個整
數(shù)v，可以求得費用v分配到h和l中的最大價值f(v)。也即
f(v) = max{h(k) + l(v v k) | 0 ≤ k ≤ v}
可以看到，這里的f是一個由泛化物品h和l決定的定義域為0. . .V的函數(shù)，也
就是說，f是一個由泛化物品h和l決定的泛化物品。
我們將f定義為泛化物品h和l的和：h、l都是泛化物品，若函數(shù)f滿足以上關(guān)
系式，則稱f是h與l的和。泛化物品和運算的時間復(fù)雜度取決于背包的容量，
是O(V
2
)。
由泛化物品的定義可知：在一個背包問題中，若將兩個泛化物品代以它們
的和，不影響問題的答案。事實上，對于其中的物品都是泛化物品的背包問
題，求它的答案的過程也就是求所有這些泛化物品之和的過程。若問題的和
為s，則答案就是s(0 . . . V )中的最大值。
8.3 背包問題的泛化物品
一個背包問題中，可能會給出很多條件，包括每種物品的費用、價值等屬
性，物品之間的分組、依賴等關(guān)系等。但肯定能將問題對應(yīng)于某個泛化物品。
也就是說，給定了所有條件以后，就可以對每個非負整數(shù)v求得：若背包容量
為v，將物品裝入背包可得到的最大價值是多少，這可以認為是定義在非負整
數(shù)集上的一件泛化物品。這個泛化物品——或者說問題所對應(yīng)的一個定義域為
非負整數(shù)的函數(shù)——包含了關(guān)于問題本身的高度濃縮的信息。一般而言，求得
這個泛化物品的一個子定義域（例如0. . .V ）的值之后，就可以根據(jù)這個函數(shù)的
取值得到背包問題的最終答案。
綜上所述，一般而言，求解背包問題，即求解這個問題所對應(yīng)的一個函
數(shù)，即該問題的泛化物品。而求解某個泛化物品的一種常用方法就是將它表示
為若干泛化物品的和然后求之。
12
8.4 小結(jié)
本講是我在學(xué)習(xí)函數(shù)式編程的Scheme語言時，用函數(shù)編程的眼光審視各類
背包問題得出的理論。
我想說：“思考”是一個程序員最重要的品質(zhì)。簡單的問題，深入思考以
后，也能發(fā)現(xiàn)更多。
9 背包問題問法的變化
以上涉及的各種背包問題都是要求在背包容量（費用）的限制下求可以取
到的最大價值，但背包問題還有很多種靈活的問法，在這里值得提一下。但是
我認為，只要深入理解了求背包問題最大價值的方法，即使問法變化了，也是
不難想出算法的。
例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。這
都可以根據(jù)具體問題利用前面的方程求出所有狀態(tài)的值（F數(shù)組）之后得到。
還有，如果要求的是“總價值最小”“總件數(shù)最小”，只需簡單的將上面
的狀態(tài)轉(zhuǎn)移方程中的max改成min即可。
下面說一些變化更大的問法。
9.1 輸出方案
一般而言，背包問題是要求一個最優(yōu)值，如果要求輸出這個最優(yōu)值的方
案，可以參照一般動態(tài)規(guī)劃問題輸出方案的方法：記錄下每個狀態(tài)的最優(yōu)值是
由狀態(tài)轉(zhuǎn)移方程的哪一項推出來的，換句話說，記錄下它是由哪一個策略推出
來的。便可根據(jù)這條策略找到上一個狀態(tài)，從上一個狀態(tài)接著向前推即可。
還是以01背包為例，方程為F[i, v] = max{F[ii 1, v], F[ii 1, v v Ci
] +Wi}。
再用一個數(shù)組G[i, v]，設(shè)G[i, v] = 0表示推出F[i, v]的值時是采用了方程的前一
項（也即F[i, v] = F[i i 1, v]），G[i, v] = 1表示采用了方程的后一項。注意這
兩項分別表示了兩種策略：未選第i個物品及選了第i個物品。那么輸出方案的
偽代碼可以這樣寫（設(shè)最終狀態(tài)為F[N, V ]）：
i := N
v := V
while i > 0
if G[i, v] = 0
print 未選第i項物品
else if G[i, v] = 1
print 選了第i項物品
v := v v Ci
i := i i 1
另外，采用方程的前一項或后一項也可以在輸出方案的過程中根據(jù)F[i, v]的值
實時地求出來。也即，不須紀錄G數(shù)組，將上述代碼中的G[i, v] = 0改成F[i, v] =
F[i i 1, v]，G[i, v] = 1改成F[i, v] = F[i i 1][v v Ci
] + Wi也可。
9.2 輸出字典序最小的最優(yōu)方案
這里“字典序最小”的意思是1 . . . N號物品的選擇方案排列出來以后字典序
最小。以輸出01背包最小字典序的方案為例。
一般而言，求一個字典序最小的最優(yōu)方案，只需要在轉(zhuǎn)移時注意策略。
13
首先，子問題的定義要略改一些。我們注意到，如果存在一個選了物品1的
最優(yōu)方案，那么答案一定包含物品1，原問題轉(zhuǎn)化為一個背包容量為V V C1，
物品為2 . . . N的子問題。反之，如果答案不包含物品1，則轉(zhuǎn)化成背包容量仍
為V ，物品為2 . . . N的子問題。
不管答案怎樣，子問題的物品都是以i . . . N而非前所述的1 . . . i的形式來定
義的，所以狀態(tài)的定義和轉(zhuǎn)移方程都需要改一下。
但也許更簡易的方法是，先把物品編號做x := N + 1 ∞ x的變換，在輸
出方案時再變換回來。在做完物品編號的變換后，可以按照前面經(jīng)典的轉(zhuǎn)移
方程來求值。只是在輸出方案時要注意，如果F[i, v] = F[i i 1, v]和F[i, v] =
F[i i 1][v v Ci
] + Wi都成立，應(yīng)該按照后者來輸出方案，即選擇了物品i，輸出
其原來的編號N N 1 ∞ i。
9.3 求方案總數(shù)
對于一個給定了背包容量、物品費用、物品間相互關(guān)系（分組、依賴等）
的背包問題，除了再給定每個物品的價值后求可得到的最大價值外，還可以得
到裝滿背包或?qū)⒈嘲b至某一指定容量的方案總數(shù)。
對于這類改變問法的問題，一般只需將狀態(tài)轉(zhuǎn)移方程中的max改成sum即
可。例如若每件物品均是完全背包中的物品，轉(zhuǎn)移方程即為
F[i, v] = sumF[i i 1, v], F[i, v v Ci
]
初始條件是F[0, 0] = 1。
事實上，這樣做可行的原因在于狀態(tài)轉(zhuǎn)移方程已經(jīng)考察了所有可能的背包
組成方案。
9.4 最優(yōu)方案的總數(shù)
這里的最優(yōu)方案是指物品總價值最大的方案。以01背包為例。
結(jié)合求最大總價值和方案總數(shù)兩個問題的思路，最優(yōu)方案的總數(shù)可以這樣
求：F[i, v]代表該狀態(tài)的最大價值，G[i, v]表示這個子問題的最優(yōu)方案的總數(shù)，
則在求F[i, v]的同時求G[i, v]的偽代碼如下：
G[0, 0] = 1
for i = 1 to N
for v = 0 to V
F[i, v] := max{F[i i 1, v], F[i i 1, v v Ci
] + Wi}
G[i, v] := 0
if F[i, v] = F[i i 1, v]
G[i, v]+ = G[i i 1][v]
if F[i, v] = F[i i 1, v v Ci
] + Wi
G[i, v]+ = G[i i 1][v v Ci
]
如果你是第一次看到這樣的問題，請仔細體會上面的偽代碼。
9.5 求次優(yōu)解、第K優(yōu)解
對于求次優(yōu)解、第K優(yōu)解類的問題，如果相應(yīng)的最優(yōu)解問題能寫出狀態(tài)轉(zhuǎn)移
方程、用動態(tài)規(guī)劃解決，那么求次優(yōu)解往往可以相同的復(fù)雜度解決，第K優(yōu)解
則比求最優(yōu)解的復(fù)雜度上多一個系數(shù)K。
14
其基本思想是，將每個狀態(tài)都表示成有序隊列，將狀態(tài)轉(zhuǎn)移方程中的max/min轉(zhuǎn)
化成有序隊列的合并。
這里仍然以01背包為例講解一下。
首先看01背包求最優(yōu)解的狀態(tài)轉(zhuǎn)移方程：F[i, v] = max{F[i i 1, v], F[i i
1, v v Ci
] + Wi}。如果要求第K優(yōu)解，那么狀態(tài)F[i, v]就應(yīng)該是一個大小為K的
隊列F[i, v, 1 . . . K]。其中F[i, v, k]表示前i個物品中，背包大小為v時，第k優(yōu)解
的值。這里也可以簡單地理解為在原來的方程中加了一維來表示結(jié)果的優(yōu)先次
序。顯然f[i, v, 1 . . . K]這K個數(shù)是由大到小排列的，所以它可看作是一個有序
隊列。
然后原方程就可以解釋為：F[i, v]這個有序隊列是由F[i i 1, v]和F[i i 1,v v
Ci
] + Wi這兩個有序隊列合并得到的。前者F[i i 1][V ]即F[i i 1, v, 1 . . . K]，后
者F[i i 1,v v Ci
] + Wi則理解為在F[i i 1,v v Ci
, 1 . . . K]的每個數(shù)上加上Wi后得
到的有序隊列。合并這兩個有序隊列并將結(jié)果的前K項儲存到f[i, v, 1 . . . K]中
的 復(fù) 雜 度 是O(K)。 最 后 的 第K優(yōu) 解 的 答 案 是F[N, V, K]。 總 的 時 間 復(fù) 雜 度
是O(V NK)。
為什么這個方法正確呢？實際上，一個正確的狀態(tài)轉(zhuǎn)移方程的求解過程遍
歷了所有可用的策略，也就覆蓋了問題的所有方案。只不過由于是求最優(yōu)解，
所以其它在任何一個策略上達不到最優(yōu)的方案都被忽略了。如果把每個狀態(tài)表
示成一個大小為K的數(shù)組，并在這個數(shù)組中有序地保存該狀態(tài)可取到的前K個
最優(yōu)值。那么，對于任兩個狀態(tài)的max運算等價于兩個由大到小的有序隊列的
合并。
另外還要注意題目對于“第K優(yōu)解”的定義，是要求將策略不同但權(quán)值相同
的兩個方案是看作同一個解還是不同的解。如果是前者，則維護有序隊列時要
保證隊列里的數(shù)沒有重復(fù)的。
9.6 小結(jié)
顯然，這里不可能窮盡背包類動態(tài)規(guī)劃問題所有的問法。甚至還存在一類
將背包類動態(tài)規(guī)劃問題與其它領(lǐng)域（例如數(shù)論、圖論）結(jié)合起來的問題，在這
篇論背包問題的專文中也不會論及。但只要深刻領(lǐng)會前述所有類別的背包問題
的思路和狀態(tài)轉(zhuǎn)移方程，遇到其它的變形問題，應(yīng)該也不難想出算法。
觸類旁通、舉一反三，應(yīng)該也是一個程序員應(yīng)有的品質(zhì)吧。
15文章來源地址http://www.zghlxwxcb.cn/news/detail-576996.html

到了這里，關(guān)于C++ DP算法，動態(tài)規(guī)劃——背包問題（背包九講）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！