有n件物品和乙個容量為v的揹包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入揹包可使價值總和最大。
這是最基礎的揹包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態：即f[i][v]表示前i件物品恰放入乙個容量為v的揹包可以獲得的最大價值。則其狀態轉移方程便是：
f[i][v]=max
這個方程非常重要，基本上所有跟揹包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的揹包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為乙個只牽扯前i-1件物品的問題。
如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的揹包中」，價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的揹包中」，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
以上方法的時間和空間複雜度均為o(vn)，其中時間複雜度應該已經不能再優化了，但空間複雜度卻可以優化到o。
先考慮上面講的基本思路如何實現，肯定是有乙個主迴圈i=1..n，每次算出來二維陣列f[i][0..v]的所有值。
那麼，如果只用乙個陣列f[0..v]，能不能保證第i次迴圈結束後f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主迴圈中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？
事實上，這要求在每次主迴圈中我們以v=v..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]儲存的是狀態f[i-1][v-c[i]]的值。偽**如下：
for i=1..n
for v=v..0
f[v]=max;
其中的f[v]=max一句恰就相當於我們的轉移方程f[i][v]=max，因為現在的f[v-c[i]]就相當於原來的f[i-1][v-c[i]]。如果將v的迴圈順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另乙個重要的揹包問題p02最簡捷的解決方案，故學習只用一維陣列解01揹包問題是十分必要的。
事實上，使用一維陣列解01揹包的程式在後面會被多次用到，所以這裡抽象出乙個處理一件01揹包中的物品過程，以後的**中直接呼叫不加說明。
過程zeroonepack，表示處理一件01揹包中的物品，兩個引數cost、weight分別表明這件物品的費用和價值。
procedure zeroonepack(cost,weight)
for v=v..cost
f[v]=max
注意這個過程裡的處理與前面給出的偽**有所不同。前面的示例程式寫成v=v..0是為了在程式中體現每個狀態都按照方程求解了，避免不必要的思維複雜度。
而這裡既然已經抽象成看作黑箱的過程了，就可以加入優化。費用為cost的物品不會影響狀態f[0..cost-1]，這是顯然的。
有了這個過程以後，01揹包問題的偽**就可以這樣寫：
for i=1..n
zeroonepack(c[i],w[i]);
我們看到的求最優解的揹包問題題目中，事實上有兩種不太相同的問法。有的題目要求「恰好裝滿揹包」時的最優解，有的題目則並沒有要求必須把揹包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿揹包，那麼在初始化時除了f[0]為0其它f[1..v]均設為-∞，這樣就可以保證最終得到的f[n]是一種恰好裝滿揹包的最優解。
如果並沒有要求必須把揹包裝滿，而是只希望**盡量大，初始化時應該將f[0..v]全部設為0。
為什麼呢？可以這樣理解：初始化的f陣列事實上就是在沒有任何物品可以放入揹包時的合法狀態。
如果要求揹包恰好裝滿，那麼此時只有容量為0的揹包可能被價值為0的nothing「恰好裝滿」，其它容量的揹包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果揹包並非必須被裝滿，那麼任何容量的揹包都有乙個合法解「什麼都不裝」，這個解的價值為0，所以初始時狀態的值也就全部為0了。
這個小技巧完全可以推廣到其它型別的揹包問題，後面也就不再對進行狀態轉移之前的初始化進行講解。
前面的偽**中有 for v=v..1，可以將這個迴圈的下限進行改進。
由於只需要最後f[v]的值，倒推前乙個物品，其實只要知道f[v-w[n]]即可。以此類推，對以第j個揹包，其實只需要知道到f[v-sum]即可，即**中的
for i=1..n
for v=v..0
可以改成
for i=1..n
bound=max,c[i]}
for v=v..bound
這對於v比較大時是有用的。
01揹包問題是最基本的揹包問題，它包含了揹包問題中設計狀態、方程的最基本思想，另外，別的型別的揹包問題往往也可以轉換成01揹包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及最後怎樣優化的空間複雜度。
有n種物品和乙個容量為v的揹包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入揹包可使這些物品的費用總和不超過揹包容量，且價值總和最大。
這個問題非常類似於01揹包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已並非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01揹包時的思路，令f[i][v]表示前i種物品恰放入乙個容量為v的揹包的最大權值。
仍然可以按照每種物品不同的策略寫出狀態轉移方程，像這樣：
f[i][v]=max
這跟01揹包問題一樣有o(vn)個狀態需要求解，但求解每個狀態的時間已經不是常數了，求解狀態f[i][v]的時間是o(v/c[i])，總的複雜度可以認為是o(v*σ(v/c[i]))，是比較大的。
將01揹包問題的基本思路加以改進，得到了這樣乙個清晰的方法。這說明01揹包問題的方程的確是很重要，可以推及其它型別的揹包問題。但我們還是試圖改進這個複雜度。
完全揹包問題有乙個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個優化的正確性顯然：
任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對於隨機生成的資料，這個方法往往會大大減少物品的件數，從而加快速度。然而這個並不能改善最壞情況的複雜度，因為有可能特別設計的資料可以一件物品也去不掉。
這個優化可以簡單的o(n^2)地實現，一般都可以承受。另外，針對揹包問題而言，比較不錯的一種方法是：首先將費用大於v的物品去掉，然後使用類似計數排序的做法，計算出費用相同的物品中價值最高的是哪個，可以o(v+n)地完成這個優化。
這個不太重要的過程就不給出偽**了，希望你能獨立思考寫出偽**或程式。
既然01揹包問題是最基本的揹包問題，那麼我們可以考慮把完全揹包問題轉化為01揹包問題來解。最簡單的想法是，考慮到第i種物品最多選v/c[i]件，於是可以把第i種物品轉化為v/c[i]件費用及價值均不變的物品，然後求解這個01揹包問題。這樣完全沒有改進基本思路的時間複雜度，但這畢竟給了我們將完全揹包問題轉化為01揹包問題的思路：
將一種物品拆成多件物品。
更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<=v。這是二進位制的思想，因為不管最優策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。
這樣把每種物品拆成o(log v/c[i])件物品，是乙個很大的改進。
但我們有更優的o(vn)的演算法。
這個演算法使用一維陣列，先看偽**：
for i=1..n
for v=0..v
f[v]=max
你會發現，這個偽**與p01的偽**只有v的迴圈次序不同而已。為什麼這樣一改就可行呢？首先想想為什麼p01中要按照v=v..
0的逆序來迴圈。這是因為要保證第i次迴圈中的狀態f[i][v]是由狀態f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮「選入第i件物品」這件策略時，依據的是乙個絕無已經選入第i件物品的子結果f[i-1][v-c[i]]。
而現在完全揹包的特點恰是每種物品可選無限件，所以在考慮「加選一件第i種物品」這種策略時，卻正需要乙個可能已選入第i種物品的子結果f[i][v-c[i]]，所以就可以並且必須採用v=0..v的順序迴圈。這就是這個簡單的程式為何成立的道理。
值得一提的是，上面的偽**中兩層for迴圈的次序可以顛倒。這個結論有可能會帶來演算法時間常數上的優化。
這個演算法也可以以另外的思路得出。例如，將基本思路中求解f[i][v-c[i]]的狀態轉移方程顯式地寫出來，代入原方程中，會發現該方程可以等價地變形成這種形式：
f[i][v]=max
將這個方程用一維陣列實現，便得到了上面的偽**。
procedure completepack(cost,weight)
利用動態規劃求解01揹包問題
演算法分析與設計 實驗報告 班級 0209404班 學號 020940410 姓名 楊洲 上機時間 2011 11 7 1 實驗目的與要求 1 掌握動態規劃演算法求解問題的一般特徵和步驟 2 使用動態規劃法程式設計，求解0 1揹包問題。2 實驗題目 利用動態規劃求解0 1揹包問題 3 實驗內容 0 ...
揹包問題的動態規劃法
揹包問題 在m件物品取出若干件放在空間為w的揹包裡，每件物品的重量為w1，w 2 wn，與之相對應的價值為p1,p2 pn。求出獲得最大價值的方案。注意 在本題中，所有的重量值均為整數。演算法分析 對於揹包問題，通常的處理方法是搜尋。用遞迴來完成搜尋，演算法設計如下 function make i ...
演算法實驗報告01揹包問題
姓名 學號 班級 一 實驗目的與要求 熟悉c c 語言的整合開發環境 通過本實驗加深對貪心演算法 動態規劃和回溯演算法的理解。二 實驗內容 掌握貪心演算法 動態規劃和回溯演算法的概念和基本思想，分析並掌握 0 1 揹包問題的三種演算法，並分析其優缺點。三 實驗程式 include int n 5 i...