背包問(wèn)題的貪心算法課件

背包問(wèn)題的貪心算法4.2背包問(wèn)題對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類(lèi)問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

---選取最優(yōu)的量度標(biāo)準(zhǔn)實(shí)為用貪心方法求解問(wèn)題的核心.24.2背包問(wèn)題背包問(wèn)題：

與0-1背包問(wèn)題類(lèi)似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

這2類(lèi)問(wèn)題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解。

3例4.3貪心算法不能求得0-1背包問(wèn)題得最優(yōu)解?？紤]背包問(wèn)題:n＝3,c＝50kg,(v1,v2,v3)=(60,100,120),(w1,w2,w3)=(10,20,30).vi/wi=(6,5,4).貪心算法解是(1,1,0),∑vixi=60+100,∑wixi=30;最優(yōu)解是(0,1,1),∑vixi=100+120,

∑wixi=50,對(duì)于0-1背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿(mǎn)，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。實(shí)際上，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問(wèn)題。44.2背包問(wèn)題已知有n種物品和一個(gè)可容納c重量的背包，每種物品i的重量為wi。假定物品i的一部分放入背包會(huì)得到vixi的效益。其中0≤xi≤1,vi>0.采用怎樣的裝包方法才會(huì)使裝入背包物品的總效益最大呢？即求解(4.2.1)(4.2.2)(4.2.3)其中（4.2.1）是目標(biāo)函數(shù)，（4.2.2）及（4.2.3）是約束條件。滿(mǎn)足約束條件的任一集合(x1,…,xn)一個(gè)可行解，使目標(biāo)函數(shù)取最大值的可行解是最優(yōu)解。5

例4.4

考慮下列情況下的背包問(wèn)題:n＝3,c＝20,(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的四個(gè)可行解是

①（1/2,1/3,1/4）16.524.25②（1,2/15,0）2028.2③（0,2/3,1）2031④（0,1,1/2）2031.5先檢驗(yàn)這四個(gè)為可行解*,即滿(mǎn)足約束條件(4.2.2),(4.2.3).再比較目標(biāo)函數(shù)值,∑vixi.知④組解效益值最大.該組解是背包問(wèn)題的最優(yōu)解。(見(jiàn)定理4.2）6（1）取目標(biāo)函數(shù)作為量度標(biāo)準(zhǔn)，即每次選擇利潤(rùn)最大的物品裝包，使背包獲得最大可能的效益值增量。在此量度標(biāo)準(zhǔn)下貪心方法就是按效益值的非增次序，將物品一一裝包，直到某一i物品放不下時(shí)，取一種能獲得最大增量的物品，將它（或其一部分）放入背包，而使最后一次裝包也符合量度標(biāo)準(zhǔn)的要求，如：還剩下兩個(gè)單位的空間，而背包外還有兩種物品。，則用j比i好，∵裝入A，;而裝入B,Vi=3。對(duì)例4.3的數(shù)據(jù)使用按效益值的非增次序的選擇策略.

例4.4n＝3,c＝20,背包剩：C－18＝2；物品2有次大效益值(V2=24)但w2=15,背包裝不下物品2。使用x2=2/15,剛好裝滿(mǎn)背包7，且物品2的24/15=v2/w2較物品3的15/10＝v3/w3效益值高。按此選擇策略,得②即(1,2/15,0),∑vixi=28.2.此解是一個(gè)次優(yōu)解。顯然，按物品效益值的非增次序裝包不能得最優(yōu)解。

原因：背包可用容量消耗過(guò)快。（2）以容量作為量度。即按物品重量的非降次序?qū)⑽锲费b包。如例4.4中的解③（讓背包盡可能慢被消耗）排序:(w3,w2,w1)=(10,15,18)V3=15,x3=1,w3=10,背包剩余C－10＝10;物品2有次大重量(w2＝15),但包裝不下。使用x2＝2/3，剛好裝滿(mǎn)背包且物品2裝入2/3與物品1裝入5/9的容量均為10個(gè)單位。但前者的效益值24×2/3=16>后者效益值＝25×5/9≈14，但③∑vixi=31,解（0，2/3，1)仍是一個(gè)次優(yōu)解。8原因：容量慢慢消耗，但效益值未能迅速增大。

（3）效益值的增長(zhǎng)速率和容量的消耗速率間取平衡的量度標(biāo)準(zhǔn)。即以單位效益為量度，使物品裝入次序按比值的非增次序排列，應(yīng)用于例4.4的數(shù)據(jù)，得解④:（0,1,1/2）,∑vixi=31.5,∑wixi=20.為例4.4背包問(wèn)題的最優(yōu)解.

---選取最優(yōu)的量度標(biāo)準(zhǔn)實(shí)為用貪心方法求解問(wèn)題的核心.9用貪心算法解背包問(wèn)題的基本步驟：

首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿(mǎn)為止。

用算法KNAPSACK可實(shí)現(xiàn)求背包問(wèn)題的最優(yōu)解.具體算法可描述如下頁(yè)：

10void

KNAPSACK(intn,floatc,floatv[],floatw[],floatx[])//v[],W[]分別含有按V[i]/W[i]≥V[i+1]/w[i+1]排序的n件物品的////效益值和重量；c是背包的容量，x[]是解向量//{inti;for(i=1;i<=n;i++)x[i]=0;//將解向量初始化為0//floatcu=c;//cu是背包剩余容量//for(i=1;i<=n;i++){if(w[i]>cu)break;x[i]=1;cu=cu-w[i];}if(i<=n)x[i]=cu/w[i];}算法4.2背包問(wèn)題的貪心算法

算法knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。當(dāng)然，為了證明算法的正確性，還必須證明背包問(wèn)題具有貪心選擇性質(zhì)。11

對(duì)于0-1背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿(mǎn)，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。 實(shí)際上，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問(wèn)題。12

定理4.2若V1/W1≥V2/W2≥…≥Vn/Wn，則算法KNAPSACK產(chǎn)生背包問(wèn)題的一個(gè)最優(yōu)解。

證明基本思想：通過(guò)將貪心法的解與任何最優(yōu)解進(jìn)行比較來(lái)證明。如果這兩個(gè)解不同，就找出不相等的且下標(biāo)最小的第一個(gè)，從中可推出與假設(shè)矛盾的結(jié)論。證明：設(shè)X＝(x1,…xn)是KNAPSACK所生成的解，如果所有xi等于1，顯然這個(gè)解就是最優(yōu)解，于是設(shè)j是使xi≠1的最小下標(biāo),由算法可知,對(duì)于1≤i<j，xi＝1;對(duì)于j<i≤n,xi＝0；對(duì)于j,0≤xi<1,如果X不是一個(gè)最優(yōu)解,則必定存在一個(gè)可行解Y=(y1,…yn),使得,∑viyi>∑vixi.不失一般性，可假定,∑wiyi=c，設(shè)k是使得yk≠xk的最小下標(biāo)，顯然，這樣的k必定存在，由上面的假設(shè)，可以推得yk<xk，這可從三種可能發(fā)生的情況，即k<j，k=j或k>j分別得到證明：13若k<j，則xk=1，因yk≠xk，從而yk<xk。若k＝j(luò)，由于,∑wixi且對(duì)于1≤i<j，有xi=yi=1

，而對(duì)j<i≤n，若xi=0，若xk<yk，顯然有∑wiyi>c，與y是可行解矛盾。若yk=xk，與假設(shè)yk≠xk矛盾，故yk<xk。若k>j，則∑wiyi>c，這是不可能的?，F(xiàn)在，假定把yk增加到xk，那么必須從(yk+1,…yn)中減去同樣多的量，使得所用的總?cè)萘咳允莄，這導(dǎo)致一個(gè)新的解Z=(z1,…,zn)，其中zi＝xi,1≤i≤k,且。因此，對(duì)于Z有14如果,∑vizi>∑viyi.，則Y不可能是最優(yōu)解。如果這兩個(gè)和數(shù)相等。同時(shí)Z＝X，則X就是最優(yōu)解；若Z＝X，則需要重復(fù)上面的討論?；蛘咦C明Y不是最優(yōu)解或者把Y轉(zhuǎn)換成X，從而證明了X也是最優(yōu)解。證畢。154.3貪心算法的基本要素

本節(jié)著重討論可以用貪心算法求解的問(wèn)題的一般特征。 對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類(lèi)問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

—選取最優(yōu)的量度標(biāo)準(zhǔn)實(shí)為用貪心方法求解問(wèn)題的核心.164.3貪心算法的基本要素1.貪心選擇性質(zhì)

所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。

動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式