對於背包問題，通常的處理方法是搜索。
用遞歸來完成搜索，算法設計如下：
function Make( i {處理到第i件物品} , j{剩余的空間為j}:integer) :integer;
初始時i=m , j=背包總容量
begin
if i:=0 then
Make:=0;
if j>=wi then (背包剩余空間可以放下物品 i )
r1:=Make(i-1,j-wi)+v; (第i件物品放入所能得到的價值 )
r2:=Make(i-1,j) (第i件物品不放所能得到的價值 )
Make:=max{r1,r2}
end;
這個算法的時間復雜度是O(2^n)，我們可以做壹些簡單的優化。
由於本題中的所有物品的體積均為整數，經過幾次的選擇後背包的剩余空間可能會相等，在搜索中會重復計算這些結點，所以，如果我們把搜索過程中計算過的結點的值記錄下來，以保證不重復計算的話，速度就會提高很多。這是簡單?quot;以空間換時間"。
我們發現，由於這些計算過程中會出現重疊的結點，符合動態規劃中子問題重疊的性質。
同時，可以看出如果通過第N次選擇得到的是壹個最優解的話，那麽第N-1次選擇的結果壹定也是壹個最優解。這符合動態規劃中最優子問題的性質。
考慮用動態規劃的方法來解決，這裏的：
階段是：在前N件物品中，選取若幹件物品放入背包中；
狀態是：在前N件物品中，選取若幹件物品放入所剩空間為W的背包中的所能獲得的最大價值；
決策是：第N件物品放或者不放；
由此可以寫出動態轉移方程：
我們用f[i,j]表示在前 i 件物品中選擇若幹件放在所剩空間為 j 的背包裏所能獲得的最大價值
f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]}
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋壹下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那麽就可以轉化為壹個只牽扯前i-1件物品的問題。如果不放第i件物品，那麽問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[v]；如果放第i件物品，那麽問題就轉化為“前i-1件物品放入剩下的容量為v-c的背包中”，此時能獲得的最大價值就是f[v-c]再加上通過放入第i件物品獲得的價值w。
這樣，我們可以自底向上地得出在前M件物品中取出若幹件放進背包能獲得的最大價值，也就是f[m,w]
算法設計如下：
procedure Make;
begin
for i:=0 to w do
f[0,i]:=0;
for i:=1 to m do
for j:=0 to w do begin
f[i,j]:=f[i-1,j];
if (j>=w) and (f[i-1,j-w]+v>f[i,j]) then
f[i,j]:=f[i-1,j-w]+v;
end;
writeln(f[m,wt]);
end;
由於是用了壹個二重循環，這個算法的時間復雜度是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[v-c]+w};
其中的f[v]=max{f[v],f[v-c]}壹句恰就相當於我們的轉移方程f[v]=max{f[v],f[v-c]}，因為現在的f[v-c]就相當於原來的f[v-c]。如果將v的循環順序從上面的逆序改成順序的話，那麽則成了f[v]由f[v-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了。
這個小技巧完全可以推廣到其它類型的背包問題，後面也就不再對進行狀態轉移之前的初始化進行講解