算法設(shè)計(jì)與分析 課件 6.2-貪心法-基本原理

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

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

但對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)題：選用貪心法還是動(dòng)態(tài)規(guī)劃求解?能用動(dòng)態(tài)規(guī)劃求解的問(wèn)題是否也能用貪心法求解?

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