解決0/1背包問題的方法有多種，最常用的有貪婪法和動(dòng)態(tài)規(guī)劃法。其中貪婪法無(wú)法得到問題的解，而動(dòng)態(tài)規(guī)劃法都可以得到解，下面是用動(dòng)態(tài)規(guī)劃法來(lái)解決0/1背包問題。
動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想是將待求解問題分解成若干個(gè)子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的，若用分治法解這類問題，則分解得到的子問題數(shù)目太多，以至于最后解決原問題需要耗費(fèi)過多的時(shí)間。動(dòng)態(tài)規(guī)劃法又和貪婪算法有些一樣，在動(dòng)態(tài)規(guī)劃中，可將一個(gè)問題的解決方案視為一系列決策的結(jié)果。不同的是，在貪婪算法中，每采用一次貪婪準(zhǔn)則便做出一個(gè)不可撤回的決策，而在動(dòng)態(tài)規(guī)劃中，還要考察每個(gè)決策序列中是否包含一個(gè)子序列。
0/1背包問題
在0 / 1背包問題中，需對(duì)容量為c 的背包進(jìn)行裝載。從n 個(gè)物品中選取裝入背包的物品，每件物品i 的重量為wi ，價(jià)值為pi 。對(duì)于可行的背包裝載，背包中物品的總重量不能超過背包的容量，裝載是指所裝入的物品價(jià)值，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示選取物品i) 取得值。
在該問題中需要決定x1 .. xn的值。假設(shè)按i = 1，2，...，n 的次序來(lái)確定xi 的值。如果置x1 = 0，則問題轉(zhuǎn)變?yōu)橄鄬?duì)于其余物品(即物品2，3，.，n)，背包容量仍為c 的背包問題。若置x1 = 1，問題就變?yōu)殛P(guān)于背包容量為c-w1 的問題。現(xiàn)設(shè)r?{c，c-w1 } 為剩余的背包容量。
在第一次決策之后，剩下的問題便是考慮背包容量為r 時(shí)的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之后的一個(gè)方案，如果不是，則會(huì)有一個(gè)更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一個(gè)更好的方案。
假設(shè)n=3, w=[100,14,10], p=[20,18,15], c= 116。若設(shè)x1 = 1，則在本次決策之后，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因?yàn)閇x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 并非策略。即x= [ 1，0，1] 可改進(jìn)為x= [ 1，1，0 ]。若設(shè)x1 = 0，則對(duì)于剩下的兩種物品而言，容量限制條件為116?？傊?，如果子問題的結(jié)果[x2，x3 ]不是剩余情況下的一個(gè)解，則[x1，x2，x3 ]也不會(huì)是總體的解。在此問題中，決策序列由決策子序列組成。假設(shè)f (i,y) 表示剩余容量為y，剩余物品為i，i + 1，...，n 時(shí)的解的值，即：利用序列由子序列構(gòu)成的結(jié)論，可得到f 的遞歸式為：
當(dāng)j>=wi時(shí)： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式
當(dāng)0<=j fn( 1 ,c) 是初始時(shí)背包問題的解。
以本題為例：若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。因此解f ( 1 , 11 6 ) = m a x {f(2，11 6)，f(2，11 6 - w1)+ p1} = m a x {f(2，11 6)，f(2，1 6)+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
現(xiàn)在計(jì)算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來(lái)需從剩余容量c-w1中尋求解，用f (2, c-w1) 表示解。依此類推，可得到所有的xi (i= 1.n) 值。
在該例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計(jì)算x2 及x3，此時(shí)r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時(shí)r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。
動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想是將待求解問題分解成若干個(gè)子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的，若用分治法解這類問題，則分解得到的子問題數(shù)目太多，以至于最后解決原問題需要耗費(fèi)過多的時(shí)間。動(dòng)態(tài)規(guī)劃法又和貪婪算法有些一樣，在動(dòng)態(tài)規(guī)劃中，可將一個(gè)問題的解決方案視為一系列決策的結(jié)果。不同的是，在貪婪算法中，每采用一次貪婪準(zhǔn)則便做出一個(gè)不可撤回的決策，而在動(dòng)態(tài)規(guī)劃中，還要考察每個(gè)決策序列中是否包含一個(gè)子序列。
0/1背包問題
在0 / 1背包問題中，需對(duì)容量為c 的背包進(jìn)行裝載。從n 個(gè)物品中選取裝入背包的物品，每件物品i 的重量為wi ，價(jià)值為pi 。對(duì)于可行的背包裝載，背包中物品的總重量不能超過背包的容量，裝載是指所裝入的物品價(jià)值，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示選取物品i) 取得值。
在該問題中需要決定x1 .. xn的值。假設(shè)按i = 1，2，...，n 的次序來(lái)確定xi 的值。如果置x1 = 0，則問題轉(zhuǎn)變?yōu)橄鄬?duì)于其余物品(即物品2，3，.，n)，背包容量仍為c 的背包問題。若置x1 = 1，問題就變?yōu)殛P(guān)于背包容量為c-w1 的問題。現(xiàn)設(shè)r?{c，c-w1 } 為剩余的背包容量。
在第一次決策之后，剩下的問題便是考慮背包容量為r 時(shí)的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之后的一個(gè)方案，如果不是，則會(huì)有一個(gè)更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一個(gè)更好的方案。
假設(shè)n=3, w=[100,14,10], p=[20,18,15], c= 116。若設(shè)x1 = 1，則在本次決策之后，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因?yàn)閇x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 并非策略。即x= [ 1，0，1] 可改進(jìn)為x= [ 1，1，0 ]。若設(shè)x1 = 0，則對(duì)于剩下的兩種物品而言，容量限制條件為116?？傊?，如果子問題的結(jié)果[x2，x3 ]不是剩余情況下的一個(gè)解，則[x1，x2，x3 ]也不會(huì)是總體的解。在此問題中，決策序列由決策子序列組成。假設(shè)f (i,y) 表示剩余容量為y，剩余物品為i，i + 1，...，n 時(shí)的解的值，即：利用序列由子序列構(gòu)成的結(jié)論，可得到f 的遞歸式為：
當(dāng)j>=wi時(shí)： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式
當(dāng)0<=j
以本題為例：若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。因此解f ( 1 , 11 6 ) = m a x {f(2，11 6)，f(2，11 6 - w1)+ p1} = m a x {f(2，11 6)，f(2，1 6)+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
現(xiàn)在計(jì)算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來(lái)需從剩余容量c-w1中尋求解，用f (2, c-w1) 表示解。依此類推，可得到所有的xi (i= 1.n) 值。
在該例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計(jì)算x2 及x3，此時(shí)r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時(shí)r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。