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