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