算法設計與分析 課件 6.2-貪心法-基本原理

信息工程大學算法設計與分析貪心法—基本原理國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版求解最優(yōu)化問題的過程包含一系列步驟每一步都有多種選擇貪心法做出在當前看來最好的選擇希望通過局部最優(yōu)選擇達到全局最優(yōu)

貪心算法總是做出當前最好的選擇，不是從整體上考慮問題的最優(yōu)性，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇，所以有時貪心算法的解不一定是整體最優(yōu)解。對于一個給定的問題，通常有多種貪心選擇策略，但不是每種策略都可以得到最優(yōu)解。因此，選擇能產生問題最優(yōu)解的貪心選擇策略是使用貪心法的核心問題。有些問題的貪心選擇策略比較直觀，有些問題則需要深入分析。適合用貪心法求解的問題一般具有兩個重要性質：貪心選擇性質（Greedy-choiceproperty）每步所做的貪心選擇最終可求得問題的最優(yōu)解最優(yōu)子結構性質（Optimalsubstructure）問題的最優(yōu)解包含子問題的最優(yōu)解1.證明所求解的問題具有最優(yōu)子結構性質。2.證明所求解的問題具有貪心選擇性質（證明每一步所做的貪心選擇最終導致問題的整體最優(yōu)解）。反之，只需要舉出一個反例，就可以說明貪心法不正確。貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質，這是它們的共同點。

但對于具有最優(yōu)子結構的問題：選用貪心法還是動態(tài)規(guī)劃求解?能用動態(tài)規(guī)劃求解的問題是否也能用貪心法求解?

給定n個物品和一個背包。物品i的重量是wi，其價值為vi，背包的容量為c。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?物品i要么全部裝入要么不裝。0-1背包問題：與0-1背包問題不同的是，在選擇物品i裝入背包時，可以選擇物品i的一部分xi，不一定要全部裝入背包，0≤xi≤1。部分背包問題：選擇題。你覺得以下哪種貪心選擇策略可以得到部分背包問題的最優(yōu)解？A.重量輕的物品優(yōu)先裝入B.價值大的物品優(yōu)先裝入C.單位重量價值大的物品優(yōu)先裝入D.以上都不對部分背包問題的貪心選擇策略有：1.重量輕優(yōu)先2.價值大優(yōu)先3.單位重量價值大優(yōu)先反例：n=2，c=5，w=(2,5)，v=(2,10)，優(yōu)先裝入物品1，再裝入物品2的一部分，得到價值總和為8；而把物品2全部裝入背包得到價值10是最優(yōu)解。反例：n=2，c=5，w=(2,5)，v=(6,10)，優(yōu)先裝入物品2，得到價值10；而先全部裝入物品1再裝入物品2的一部分，得到價值12是最優(yōu)解。錯誤錯誤該策略綜合考慮到物品重量和價值兩個因素，可以得到最優(yōu)解。正確對物品按單位重量價值vi/wi從大到小排序；根據貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包；若背包內的物品總重量未超過c，則選擇單位重量價值次高的物品并盡可能多地裝入背包；依此策略進行下去，直到背包裝滿為止。貪心法求解部分背包問題的步驟：貪心法求解部分背包問題的代碼：voidKnapsack(intn,floatc,float*v,float*w,float*x){knap_sort(n,v,w);/*按單位重量價值從大到小排序*/for(i=1;i<=n;i++)x[i]=0;floatleft=c;/*逐一判斷每件物品*/for(i=1;i<=n;i++){if(w[i]>left)break;x[i]=1;left-=w[i];}if(i<=n)x[i]=left/w[i];/*可能有部分裝入的物品*/}時間復雜度為O(nlogn)例：c=7,(w1,w2,w3)=(3,4,5),(v1,v2,v3)=(5,6,10)。貪心法得到的最大價值為10，裝入物品3。實際最大價值為11，裝入物品1和2。貪心法不能正確求解0-1背包問題。原因：無法保證最終能將背包裝滿，部分閑置的背包空間使背包的單位空間的價值降低。在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再做出最好的選擇。由此就出現(xiàn)許多互相重疊的子問題。0-1背包問題可用動態(tài)規(guī)劃求解。貪心法不能正確求解0-1背包問題。動態(tài)規(guī)劃貪心共同點最優(yōu)子結構性質不同點重疊子問題貪心選擇性質求解思路對所有選擇比較后決定最優(yōu)的只考慮一種選擇，因而更高效解題過程通常采取自底而上，從小問題推出大問題從大問題逐步求解，不斷減少問題規(guī)模，直至結束代碼結構