在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即n ?i=1pi xi 取得最大值。約束條件為n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。 在這個表達式中，需求出xt 的值。xi = 1表示物品i 裝入背包中，xi =0 表示物品i 不裝入背包。0 / 1背包問題是一個一般化的貨箱裝載問題，即每個貨箱所獲得的價值不同。貨箱裝載問題轉化為背包問題的形式為：船作為背包，貨箱作為可裝入背包的物品。 例1-8 在雜貨店比賽中你獲得了第一名，獎品是一車免費雜貨。店中有n 種不同的貨物。規則規定從每種貨物中最多只能拿一件，車子的容量為c，物品i 需占用wi 的空間，價值為pi 。你的目標是使車中裝載的物品價值最大。當然，所裝貨物不能超過車的容量，且同一種物品不得拿走多件。這個問題可仿照0 / 1背包問題進行建模，其中車對應于背包，貨物對應于物品。 0 / 1背包問題有好幾種貪婪策略，每個貪婪策略都采用多步過程來完成背包的裝入。在每一步過程中利用貪婪準則選擇一個物品裝入背包。一種貪婪準則為：從剩余的物品中，選出可以裝入背包的價值最大的物品，利用這種規則，價值最大的物品首先被裝入（假設有足夠容量），然后是下一個價值最大的物品，如此繼續下去。這種策略不能保證得到最優解。例如，考慮n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。當利用價值貪婪準則時，獲得的解為x= [ 1 , 0 , 0 ]，這種方案的總價值為2 0。而最優解為[ 0 , 1 , 1 ]，其總價值為3 0。 另一種方案是重量貪婪準則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規則對于前面的例子能產生最優解，但在一般情況下則不一定能得到最優解。考慮n= 2 ,w=[10,20], p=[5,100], c= 2 5。當利用重量貪婪策略時，獲得的解為x =[1,0], 比最優解[ 0 , 1 ]要差。 還可以利用另一方案，價值密度pi /wi 貪婪算法，這種選擇準則為：從剩余物品中選擇可 裝入包的pi /wi 值最大的物品，這種策略也不能保證得到最優解。利用此策略試解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 時的最優解。 我們不必因所考察的幾個貪婪算法都不能保證得到最優解而沮喪， 0 / 1背包問題是一個N P-復雜問題。對于這類問題，也許根本就不可能找到具有多項式時間的算法。雖然按pi /wi 非遞（增）減的次序裝入物品不能保證得到最優解，但它是一個直覺上近似的解。我們希望它是一個好的啟發式算法，且大多數時候能很好地接近最后算法。在6 0 0個隨機產生的背包問題中，用這種啟發式貪婪算法來解有2 3 9題為最優解。有5 8 3個例子與最優解相差1 0 %，所有6 0 0個答案與最優解之差全在2 5 %以內。該算法能在O (nl o gn)時間內獲得如此好的性能。我們也許會問，是否存在一個x (x<1 0 0 )，使得貪婪啟發法的結果與最優值相差在x%以內。答案是否定的。為說明這一點，考慮例子n =2, w = [ 1 ,y], p= [ 1 0 , 9y], 和c= y。貪婪算法結果為x=[1,0], 這種方案的值為1 0。對于y≥1 0 / 9，最優解的值為9 y。因此，貪婪算法的值與最優解的差對最優解的比例為( ( 9y - 1 0)/9y* 1 0 0 ) %，對于大的y，這個值趨近于1 0 0 %。但是可以建立貪婪啟發式方法來提供解，使解的結果與最優解的值之差在最優值的x% (x<100) 之內。首先將最多k 件物品放入背包，假如這k 件物品重量大于c，則放棄它。否則，剩余的容量用來考慮將剩余物品按pi /wi 遞減的順序裝入。通過考慮由啟發法產生的解法中最多為k 件物品的所有可能的子集來得到最優解。 例13-9 考慮n =4, w=[2,4,6,7], p=[6,10,12,13], c = 11。當k= 0時，背包按物品價值密度非遞減順序裝入，首先將物品1放入背包，然后是物品2，背包剩下的容量為5個單元，剩下的物品沒有一個合適的，因此解為x = [ 1 , 1 , 0 , 0 ]。此解獲得的價值為1 6。 現在考慮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 ]，獲得的價值為1 8。若從子集{ 4 }開始，產生的解為x = [ 1 , 0 , 0 , 1 ]，獲得的價值為1 9。考慮子集大小為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 ]，這些結果中最后一個價值為2 3，它的值比k= 0和k= 1時獲得的解要高，這個答案即為啟發式方法產生的結果。 這種修改后的貪婪啟發方法稱為k階優化方法（k - o p t i m a l）。也就是，若從答案中取出k 件物品，并放入另外k 件，獲得的結果不會比原來的好，而且用這種方式獲得的值在最優值的( 1 0 0 / (k + 1 ) ) %以內。當k= 1時，保證最終結果在最佳值的5 0 %以內；當k= 2時，則在3 3 . 3 3 %以內等等，這種啟發式方法的執行時間隨k 的增大而增加，需要測試的子集數目為O (nk )，每一個子集所需時間為O (n)，因此當k >0時總的時間開銷為O (nk+1 )。實際觀察到的性能要好得多。
