0/1背包問(wèn)題有好幾種貪婪策略，每個(gè)貪婪策略都采用多步過(guò)程來(lái)完成背包的裝入，在每一步過(guò)程中利用貪婪準(zhǔn)則選擇一個(gè)物品裝入背包。
1、從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品。利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。例如，n=2, weight=[100, 10, 10], prize=[20, 15, 15], count=105。當(dāng)利用價(jià)值貪婪準(zhǔn)則時(shí)，獲得的解為x= [1, 0, 0]，這種方案的總價(jià)值為20。而最優(yōu)解為[0, 1, 1]，其總價(jià)值為30。
2、重量貪婪準(zhǔn)則：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規(guī)則對(duì)于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解。考慮n=2 ,w=[10,20], p=[5,100], c=25。當(dāng)利用重量貪婪策略時(shí)，獲得的解為x =[1,0], 比最優(yōu)解[0, 1]要差。
3、還可以利用另一方案，價(jià)值密度pi/wi 貪婪算法，這種選擇準(zhǔn)則為：從剩余物品中選擇可裝入包的pi/wi值最大的物品。這種策略也不能保證得到最優(yōu)解，利用此策略試解n=3 ,w=[20,15,15], p=[40,25,25], c=30 時(shí)的最優(yōu)解。
我們不必因所考察的幾個(gè)貪婪算法都不能保證得到最優(yōu)解而沮喪，0/1背包問(wèn)題是一個(gè)NP-復(fù)雜問(wèn)題，對(duì)于這類(lèi)問(wèn)題，也許根本就不可能找到具有多項(xiàng)式時(shí)間的算法。雖然按pi/wi非遞（增）減的次序裝入物品不能保證得到最優(yōu)解，但它是一個(gè)直覺(jué)上近似的解。我們希望它是一個(gè)好的啟發(fā)式算法，且大多數(shù)時(shí)候能很好地接近最后算法。在600個(gè)隨機(jī)產(chǎn)生的背包問(wèn)題中，用這種啟發(fā)式貪婪算法來(lái)解有239題為最優(yōu)解。有583個(gè)例子與最優(yōu)解相差10%，所有600個(gè)答案與最優(yōu)解之差全在25%以內(nèi)。該算法能在O(nlogn)時(shí)間內(nèi)獲得如此好的性能。我們也許會(huì)問(wèn)，是否存在一個(gè)x(x<100)，使得貪婪啟發(fā)法的結(jié)果與最優(yōu)值相差在x%以內(nèi)？答案是否定的。考慮例子n=2,w=[1,y],p=[10,9y],c=y。貪婪算法結(jié)果為x=[1,0], 這種方案的值為10。對(duì)于y≥10/9，最優(yōu)解的值為9y。因此，貪婪算法的值與最優(yōu)解的差對(duì)最優(yōu)解的比例為((9y-10)/9y*100)%，對(duì)于大的y，這個(gè)值趨近于100%。
可以建立貪婪啟發(fā)式方法來(lái)提供解，使解的結(jié)果與最優(yōu)解的值之差在最優(yōu)值的x%(x<100)之內(nèi)。首先將最多k件物品放入背包，假如這k件物品重量大于c，則放棄它。否則，剩余的容量用來(lái)考慮將剩余物品按pi/wi遞減的順序裝入。通過(guò)考慮由啟發(fā)法產(chǎn)生的解法中最多為k件物品的所有可能的子集來(lái)得到最優(yōu)解。
例：考慮n=4, w=[2,4,6,7], p=[6,10,12,13], c=11。
當(dāng)k=0時(shí)，背包直接按物品價(jià)值密度非遞減順序裝入，首先將物品1放入背包，然后是物品2，背包剩下的容量為5個(gè)單元，剩下的物品沒(méi)有一個(gè)合適的，因此解為x=[1,1,0,0]。此解獲得的價(jià)值為16。
現(xiàn)在考慮k=1時(shí)的貪婪啟發(fā)法。最初的子集為{1},{2},{3},{4}。子集{1},{2}產(chǎn)生與k=0時(shí)相同的結(jié)果，考慮子集{3}，置x3為1。此時(shí)還剩5個(gè)單位的容量，按價(jià)值密度非遞增順序來(lái)考慮如何利用這5個(gè)單位的容量。首先考慮物品1，它適合，因此取x1為1，這時(shí)僅剩下3個(gè)單位容量了，且剩余物品沒(méi)有能夠加入背包中的物品。通過(guò)子集{3}開(kāi)始求解得結(jié)果為x=[1,0,1,0]，獲得的價(jià)值為18。若從子集{4}開(kāi)始，產(chǎn)生的解為x = [1,0,0,1]，獲得的價(jià)值為19。考慮k為0和1時(shí)獲得的最優(yōu)解為[1,0,0,1]。這個(gè)解是通過(guò)k=1的貪婪啟發(fā)式算法得到的。
若k=2，除了考慮k<2的子集，還必需考慮子集{1,2},{1,3},{1,4},{2,3},{2,4}和{3,4}。首先從最后一個(gè)子集開(kāi)始，它是不可行的，故將其拋棄，剩下的子集經(jīng)求解分別得到如下結(jié)果：[1,1,0,0],[1,0,1,0],[1,0,0,1],[0,1,1,0]和[0,1,0,1]，這些結(jié)果中最后一個(gè)價(jià)值為23，它的值比k=0和k=1時(shí)獲得的解要高，這個(gè)答案即為啟發(fā)式方法產(chǎn)生的結(jié)果。
這種修改后的貪婪啟發(fā)方法稱(chēng)為k階優(yōu)化方法（k-optimal）。也就是，若從答案中取出k件物品，并放入另外k件，獲得的結(jié)果不會(huì)比原來(lái)的好，而且用這種方式獲得的值在最優(yōu)值的(100/(k+1))%以內(nèi)。當(dāng)k= 1時(shí)，保證最終結(jié)果在最佳值的50%以內(nèi)；當(dāng)k=2時(shí)，則在33.33%以內(nèi)等等，這種啟發(fā)式方法的執(zhí)行時(shí)間隨k的增大而增加，需要測(cè)試的子集數(shù)目為O(nk)，每一個(gè)子集所需時(shí)間為O(n)，因此當(dāng)k>0時(shí)總的時(shí)間開(kāi)銷(xiāo)為O (nk+1)。實(shí)際觀察到的性能要好得多。
PS:
背包是np完全問(wèn)題。網(wǎng)上還有動(dòng)態(tài)規(guī)劃算法:
f(i, x) = max{f(i-1, x-W[i]) + C[i], f(i-1, x)} 最終解f(n, p)。
還有分支限界法，感覺(jué)跟遞歸沒(méi)區(qū)別。
甚至還有遺傳算法……