01背包是在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2至Wn，與之相對應的價值為P1,P2至Pn。01背包是背包問題中最簡單的問題。01背包的約束條件是給定幾種物品，每種物品有且只有一個，並且有權值和體積兩個屬性。在01背包問題中，因為每種物品只有一個，對於每個物品只需要考慮選與不選兩種情況。如果不選擇將其放入背包中，則不需要處理。如果選擇將其放入背包中，由於不清楚之前放入的物品占據了多大的空間，需要枚舉將這個物品放入背包後可能占據背包空間的所有情況。
基本介紹
- 中文名：01背包
- 外文名：01bag
- 條件：M件物品取出若干放空間W的背包里
- 問題：求出獲得最大價值的方案
- 類別：數學問題，計算機問題
- 時間複雜度：O(VN)
- 空間複雜度：O(VN)
背包問題,基本概念,問題雛形,問題描述,算法分析,解決方案,最佳化複雜度,細節問題,小結,例題,
背包問題
基本概念
問題雛形
01背包題目的雛形是：
有N件物品和一個容量為V的背包。第i件物品的體積是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
從這個題目中可以看出，01背包的特點就是：每種物品僅有一件，可以選擇放或不放。
其狀態轉移方程是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
對於這方方程其實並不難理解，方程之中，現在需要放置的是第i件物品，這件物品的體積是c[i],價值是w[i],因此f[i-1][v]代表的就是不將這件物品放入背包，而f[i-1][v-c[i]]+w[i]則是代表將第i件放入背包之後的總價值，比較兩者的價值，得出最大的價值存入現在的背包之中。
理解了這個方程後，將方程代入實際題目的套用之中，可得
for (i = 1; i <= n; i++) for (j = v; j >= c[i]; j--)//在這裡，背包放入物品後，容量不斷的減少，直到再也放不進了 f[i][j] = max(f[i - 1][j], f[i - 1][j - c[i]] + w[i]);
問題描述
求出獲得最大價值的方案。
注意：在本題中，所有的體積值均為整數。
算法分析
對於背包問題，通常的處理方法是搜尋。
用遞歸來完成搜尋，算法設計如下：
int make(int i, int j)//處理到第i件物品,剩餘的空間為j 初始時i=m , j=背包總容量{ if (i == 0) return 0; if (j >= c[i])//(背包剩餘空間可以放下物品 i ) { int r1 = make(i - 1, j - w[i]);//第i件物品放入所能得到的價值 int r2 = make(i - 1, j);//第i件物品不放所能得到的價值 return min(r1, r2); } return make(i - 1, j);//放不下物品 i }這個算法的時間複雜度是O(n^2)，我們可以做一些簡單的最佳化。
由於本題中的所有物品的體積均為整數，經過幾次的選擇後背包的剩餘空間可能會相等，在搜尋中會重複計算這些結點，所以，如果我們把搜尋過程中計算過的結點的值記錄下來，以保證不重複計算的話，速度就會提高很多。這是簡單的“以空間換時間”。
我們發現，由於這些計算過程中會出現重疊的結點，符合動態規劃中子問題重疊的性質。
同時，可以看出如果通過第N次選擇得到的是一個最優解的話，那么第N-1次選擇的結果一定也是一個最優解。這符合動態規劃中最優子問題的性質。
解決方案
考慮用動態規劃的方法來解決，這裡的：
階段：在前N件物品中，選取若干件物品放入背包中
狀態：在前N件物品中，選取若干件物品放入所剩空間為W的背包中的所能獲得的最大價值
決策：第N件物品放或者不放
由此可以寫出動態轉移方程：
我們用f[i][j]表示在前 i 件物品中選擇若干件放在已用空間為 j 的背包里所能獲得的最大價值
f[i][j] = max(f[i - 1][j - W[i]] + P[i], f[i - 1][j]);//j >= W[ i ]
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[v]；如果放第i件物品，那么問題就轉化為“前i-1件物品放入已用的容量為c的背包中”，此時能獲得的最大價值就是f[c]再加上通過放入第i件物品獲得的價值w。
這樣，我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值，也就是f[m,w]
算法設計如下：
int main(){ cin >> n >> v; for (int i = 1; i <= n; i++) cin >> c[i];//價值 for (int i = 1; i <= n; i++) cin >> w[i];//體積 for (int i = 1; i <= n; i++) f[i][0] = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= v; j++) if (j >= w[i])//背包容量夠大 f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]); else//背包容量不足 f[i][j] = f[i - 1][j]; cout << f[n][v] << endl; return 0;}由於是用了一個二重循環，這個算法的時間複雜度是O（n*w)。而用搜尋的時候，當出現最壞的情況，也就是所有的結點都沒有重疊，那么它的時間複雜度是O（2^n)。看上去前者要快很多。但是，可以發現在搜尋中計算過的結點在動態規劃中也全都要計算，而且這裡算得更多（有一些在最後沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。
事實上，由於我們定下的前提是：所有的結點都沒有重疊。也就是說，任意N件物品的重量相加都不能相等，而所有物品的重量又都是整數，那么這個時候W的最小值是：1+2+2^2+2^3+……+2^n-1=2^n -1
此時n*w>2^n，動態規劃比搜尋還要慢~~|||||||所以，其實背包的總容量W和重疊的結點的個數是有關的。
考慮能不能不計算那些多餘的結點……
最佳化複雜度
以上方法的時間和空間複雜度均為O(N*V)，其中時間複雜度基本已經不能再最佳化了，但空間複雜度卻可以最佳化到O(V)。
for i=1..N
for v=V..0
f[v]=max{f[v],f[c]+w};
其中的f[v]=max{f[v],f[c]}一句恰就相當於我們的轉移方程f[v]=max{f[v],f[c]}，因為現在的f[c]就相當於原來的f[c]。如果將v的循環順序從上面的逆序改成順序的話，那么則成了f[v]由f[c]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數組解01背包問題是十分必要的。
事實上，使用一維數組解01背包的程式在後面會被多次用到，所以這裡抽象出一個處理一件01背包中的物品過程，以後的代碼中直接調用不加說明。
過程ZeroOnePack，表示處理一件01背包中的物品，兩個參數cost、weight分別表明這件物品的費用和價值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意這個過程里的處理與前面給出的偽代碼有所不同。前面的示例程式寫成v=V..0是為了在程式中體現每個狀態都按照方程求解了，避免不必要的思維複雜度。而這裡既然已經抽象成看作黑箱的過程了，就可以加入最佳化。費用為cost的物品不會影響狀態f[0..cost-1]，這是顯然的。
有了這個過程以後，01背包問題的偽代碼就可以這樣寫：
for i=1..N
ZeroOnePack(c,w);
細節問題
如果是第一種問法，要求恰好裝滿背包，那么在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。
如果並沒有要求必須把背包裝滿，而是只希望價格儘量大，初始化時應該將f[0..V]全部設為0。
為什麼呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那么此時只有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果背包並非必須被裝滿，那么任何容量的背包都有一個合法解“什麼都不裝”，這個解的價值為0，所以初始時狀態的值也就全部為0了。
這個小技巧完全可以推廣到其它類型的背包問題，後面也就不再對進行狀態轉移之前的初始化進行講解。
小結
01背包問題是最基本的背包問題，它包含了背包問題中設計狀態、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及最後怎樣最佳化的空間複雜度。
例題
裝箱問題
描述 Description ：
有一個箱子容量為V（正整數，0≤V≤20000），同時有n個物品（0小於n≤30），每個物品有一個體積（正整數）。要求從n個物品中，任取若干個裝入箱內，使箱子的剩餘空間為最小。
輸入v，n，在輸入n個物品。
輸出箱子的剩餘空間為最小。
輸入 Input ：
24 （一個整數，表示箱子容量）
6 （一個整數 [ 即n ] ，表示有n個物品）
8 （接下來n行，分別表示這n個物品的各自體積。）
3
12
7
9
7
輸出 Output
0 （ 一個整數，表示箱子剩餘空間。）
分析
轉化為01背包，認為每個物品的價值相等，用0/1背包求出價值最大值，在用空間減去價值最大值即可
Pascal 程式
var v,n,i,j,k:longint;f:array[0..20000]of boolean;a:array[1..30]of longint;beginread(v,n);for i:=1 to n do read(a[i]);f[0]:=true;for i:=1 to n dofor j:=v downto a[i] doif not f[j] and f[j-a[i]] thenf[j]:=true;k:=v;while (k>1)and(not f[k]) do dec(k);writeln(v-k);end.
C++程式
#include<iostream>int v, n, i, j, k, a[31];bool f[20001];int main(){ using namespace std; cin >> v >> n; for (int i = 1; i <= n; i++) cin >> a[i]; f[0] = 1; for (int i = 1; i <= n; i++) for (int j = v; j >= a[i]; j--) if (!f[j] && f[j - a[i]]) f[j] = 1; for (k = v; k > 1 && !f[k]; k--) cout << v - k << endl; return 0;}