背包問題
基本概念
問題雛形
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件放入背包之後的總價值，比較兩者的價值，得出最大的價值存入現在的背包之中。
理解了這個方程後，將方程代入實際題目的套用之中，可得
問題描述
求出獲得最大價值的方案。
注意：在本題中，所有的體積值均為整數。
算法分析
對於背包問題，通常的處理方法是搜尋。
用遞歸來完成搜尋，算法設計如下：
這個算法的時間複雜度是O(n^2)，我們可以做一些簡單的最佳化。
由於本題中的所有物品的體積均為整數，經過幾次的選擇後背包的剩餘空間可能會相等，在搜尋中會重複計算這些結點，所以，如果我們把搜尋過程中計算過的結點的值記錄下來，以保證不重複計算的話，速度就會提高很多。這是簡單的“以空間換時間”。
我們發現，由於這些計算過程中會出現重疊的結點，符合 動態規劃中子問題重疊的性質。
同時，可以看出如果通過第N次選擇得到的是一個最優解的話，那么第N-1次選擇的結果一定也是一個最優解。這符合動態規劃中最優子問題的性質。
解決方案
考慮用動態規劃的方法來解決，這裡的：
階段：在前N件物品中，選取若干件物品放入背包中
狀態：在前N件物品中，選取若干件物品放入所剩空間為W的背包中的所能獲得的最大價值
決策：第N件物品放或者不放
由此可以寫出動態轉移方程：
我們用f[i][j]表示在前 i 件物品中選擇若干件放在已用空間為 j 的背包里所能獲得的最大價值
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[v]；如果放第i件物品，那么問題就轉化為“前i-1件物品放入已用的容量為c的背包中”，此時能獲得的最大價值就是f[c]再加上通過放入第i件物品獲得的價值w。
這樣，我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值，也就是f[m,w]
算法設計如下：
由於是用了一個二重循環，這個算法的時間複雜度是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)。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[0..V]的所有值。那么，如果只用一個數組f[0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[v]呢？f[v]是由f[v]和f[v-c]兩個子問題遞推而來，能否保證在推f[v]時（也即在第i次主循環中推f[v]時）能夠得到f[v]和f[v-c]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c]保存的是狀態f[v-c]的值。偽代碼如下：
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 程式
C++程式
