算法設(shè)計(jì)與分析課件

第一章算法概述第二章遞歸與分治策略第三章動(dòng)態(tài)規(guī)劃第四章貪心算法第五章回朔法第六章分支限界法第七章隨機(jī)化算法算法設(shè)計(jì)與分析>目錄1ppt課件第一章算法概述第二章遞歸與分治策略第三章動(dòng)態(tài)規(guī)劃4.2貪心算法基本要素4.1活動(dòng)安排問(wèn)題4.3最優(yōu)裝載問(wèn)題算法設(shè)計(jì)與分析>目錄4.7多機(jī)調(diào)度問(wèn)題2ppt課件4.2貪心算法基本要素4.1活動(dòng)安排問(wèn)題4.3最優(yōu)裝載算法設(shè)計(jì)與分析>

貪心算法4.1活動(dòng)安排問(wèn)題有n個(gè)活動(dòng)E={1,2,…,n},其中每個(gè)活動(dòng)要使用同一資源,同一時(shí)間只允許一個(gè)活動(dòng)使用該資源.每個(gè)活動(dòng)i都有一個(gè)開始時(shí)間si,和一個(gè)結(jié)束時(shí)間fi.如果選擇活動(dòng)i,則它在時(shí)間區(qū)間[si,fi

)內(nèi)占用該資源;若區(qū)間[si,fi

)與[sj,fj

)不相交,則稱活動(dòng)i與j是相容的(兼容的).活動(dòng)安排問(wèn)題是要求在所給的活動(dòng)集合中選出最大相容活動(dòng)子集.3ppt課件算法設(shè)計(jì)與分析>貪心算法4.1活動(dòng)安排問(wèn)題有n個(gè)活動(dòng)E在安排時(shí)應(yīng)該將結(jié)束時(shí)間早的活動(dòng)盡量往前安排，好給后面的活動(dòng)安排留出更多的空間，從而達(dá)到安排最多活動(dòng)的目標(biāo)。貪心準(zhǔn)則應(yīng)當(dāng)是：在未安排的活動(dòng)中挑選結(jié)束時(shí)間最早的活動(dòng)安排。算法設(shè)計(jì)與分析>

貪心算法[直觀想法]4ppt課件在安排時(shí)應(yīng)該將結(jié)束時(shí)間早的活動(dòng)盡量往前安排，好給后面的活動(dòng)安算法設(shè)計(jì)與分析>

貪心算法[算法思路]1.將活動(dòng)按結(jié)束時(shí)間排序,得到活動(dòng)集E={e1,e2…en}；2.先將e1選入結(jié)果集合A中，即A={e1}；3.依次掃描每一個(gè)活動(dòng)ei:如果ei的si

>最后一個(gè)選入A的活動(dòng)ej的fj

,則將ei選入A中,否則放棄ei。5ppt課件算法設(shè)計(jì)與分析>貪心算法[算法思路]5ppt課件算法設(shè)計(jì)與分析>

貪心算法定理：考慮任意非空子問(wèn)題Sk，令am是Sk中結(jié)束時(shí)間最早的活動(dòng)，則am在Sk的某個(gè)最大兼容活動(dòng)子集中。證明：令A(yù)k是Sk的一個(gè)最大兼容活動(dòng)子集，且aj是Ak中結(jié)束時(shí)間最早的活動(dòng)。若aj=am，則證明am在Sk的某個(gè)最大兼容活動(dòng)子集中。若aj≠am，令集合,即將Ak中的aj替換am因?yàn)锳k中的活動(dòng)都是不相交的，aj是Ak中結(jié)束時(shí)間最早的活動(dòng)，而fm≤fj

，所以Ak′中的活動(dòng)都是不相交的。由于|

Ak′|=|

Ak|，因此得出結(jié)論Ak′也是Sk的一個(gè)最大活動(dòng)子集，且它包含am。6ppt課件算法設(shè)計(jì)與分析>貪心算法定理：考慮任意非空子問(wèn)題Sk，令2.最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。算法設(shè)計(jì)與分析>

貪心算法7ppt課件2.最優(yōu)子結(jié)構(gòu)性質(zhì)算法設(shè)計(jì)與分析>貪心算法7ppt課件3.貪心算法與動(dòng)態(tài)規(guī)劃算法的差異

算法設(shè)計(jì)與分析>

貪心算法相同點(diǎn)：都具有最優(yōu)子結(jié)構(gòu)性質(zhì)區(qū)別：動(dòng)態(tài)規(guī)劃法貪心算法選擇特征往往依賴于相關(guān)子問(wèn)題的解。只有解出相關(guān)子問(wèn)題才能作出選擇。當(dāng)前狀態(tài)下作出最好選擇，即局部最優(yōu)選擇，但不依賴于子問(wèn)題的解設(shè)計(jì)特征自底向上自頂向下8ppt課件3.貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 算法設(shè)計(jì)與分析>貪心算算法設(shè)計(jì)與分析>

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

給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

在選擇物品i裝入背包時(shí)，可以選擇物品i的部分，而不一定要全部裝入背包，1≤i≤n。不允許重復(fù)裝入。9ppt課件算法設(shè)計(jì)與分析>貪心算法背包問(wèn)題9ppt課件

于是，背包問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件，并使目標(biāo)函數(shù)達(dá)到最大的解向量X=(x1,x2,…,xn)。設(shè)xi表示物品i裝入背包的情況，根據(jù)問(wèn)題的要求，有如下約束條件和目標(biāo)函數(shù)：算法設(shè)計(jì)與分析>

貪心算法10ppt課件于是，背包問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件，并每次撿最輕的物品裝；每次撿價(jià)值最大的裝；每次裝包時(shí)既考慮物品的重量又考慮物品的價(jià)值，也就是說(shuō)每次撿單位價(jià)值最大的裝。算法設(shè)計(jì)與分析>

貪心算法貪心選擇：

只考慮到多裝些物品，但由于單位價(jià)值未必高，總價(jià)值不能達(dá)到最大；每次選擇的價(jià)值最大，但同時(shí)也可能占用了較大的空間，裝的物品少，未必能夠達(dá)到總價(jià)值最大確實(shí)能夠達(dá)到總價(jià)值最大。11ppt課件每次撿最輕的物品裝；算法設(shè)計(jì)與分析>貪心算法貪心選擇：首先計(jì)算每種物品單位重量的價(jià)值vi/wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略處理，直到背包裝滿為止。算法設(shè)計(jì)與分析>

貪心算法基本步驟：

12ppt課件首先計(jì)算每種物品單位重量的價(jià)值vi/wi，然后，依貪心選擇策算法設(shè)計(jì)與分析>

貪心算法voidKnapsack(intn,floatM,floatv[],floatw[],floatx[])//價(jià)值數(shù)組v[1:n]、重量數(shù)組w[1:n];

//它們?cè)氐呐帕许樞驖M足v[i]/w[i]≥v[i+1]/w[i+1];

//M是背包容量，x是解向量.

{floatc=M;

//使背包剩余容量初始化為M

int

i;Sort(n,v,w);

for(i=1;i<=n;i++)x[i]=0;//將解向量初始化為零

for(i=1;i<=n;i++){ifw[i]>cbreak;x[i]=1;c=c-w[i];}

if(

in)x[i]=c/w[i];}將各種物品依其單位重量的價(jià)值從大到小排序。算法的計(jì)算時(shí)間上界為O(nlogn)。13ppt課件算法設(shè)計(jì)與分析>貪心算法voidKnapsack(i0-1背包問(wèn)題：

給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。算法設(shè)計(jì)與分析>

貪心算法14ppt課件0-1背包問(wèn)題：在選擇裝入背包的物品時(shí)，對(duì)每種物品算法設(shè)計(jì)與分析>

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

15ppt課件算法設(shè)計(jì)與分析>貪心算法對(duì)于0-1背包問(wèn)題，貪心選擇之所算法設(shè)計(jì)與分析>

貪心算法4.3最優(yōu)裝載

有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為wi。最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。[問(wèn)題描述]滿足16ppt課件算法設(shè)計(jì)與分析>貪心算法4.3最優(yōu)裝載 1.算法描述

最優(yōu)裝載問(wèn)題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問(wèn)題的最優(yōu)解。算法設(shè)計(jì)與分析>

貪心算法17ppt課件1.算法描述算法設(shè)計(jì)與分析>貪心算法17ppt課件算法設(shè)計(jì)與分析>

貪心算法voidLoading(intx[],Typew[],floatc,intn){int*t=newint[n+1];Sort.(w,t,n);for(inti=0;i<n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}t[i]中存儲(chǔ)第i輕集裝箱在原來(lái)序列中的下標(biāo)x[i]記載第i個(gè)集裝箱是否裝入,x[i]=1裝入,x[i]=0未裝入18ppt課件算法設(shè)計(jì)與分析>貪心算法voidLoading(int物品重量分別為15，10，27，18，船載重為50定義：w[]={15,10,27,18}物品重量

T[]={1,0,3,2}物品從輕到重排序后序號(hào)

C=50船載重貪心算法計(jì)算步驟：

w[T[0]]=10<c,c=c-10=40

w[T[1]]=15<c,c=c-15=25

w[T[2]]=18<c,c=c-18=7

w[T[3]]=27>c算法設(shè)計(jì)與分析>

貪心算法[例]19ppt課件物品重量分別為15，10，27，18，船載重為50算法設(shè)計(jì)與算法設(shè)計(jì)與分析>

貪心算法2.貪心選擇性質(zhì)設(shè)貨箱已經(jīng)從小到大排序，是最優(yōu)裝載問(wèn)題的一個(gè)最優(yōu)解，又設(shè)如果給定的最優(yōu)裝載問(wèn)題有解，則1≤k≤n（1）當(dāng)k=1時(shí)，是一個(gè)滿足貪婪選擇性質(zhì)的最優(yōu)解。（2）當(dāng)k>1時(shí)，則因此，所給最優(yōu)裝載問(wèn)題的一個(gè)可行解，且是最優(yōu)解。

20ppt課件算法設(shè)計(jì)與分析>貪心算法2.貪心選擇性質(zhì)設(shè)貨箱已經(jīng)從小到設(shè)[x1,...,xn

]是最優(yōu)裝載問(wèn)題的一個(gè)滿足貪心選擇性質(zhì)的最優(yōu)解，則x1=1時(shí),[x2,...,xn

]是輪船載重量為c-w1且待裝集裝箱為{2,...,n}時(shí)相應(yīng)最優(yōu)裝載問(wèn)題的一個(gè)最優(yōu)解。算法設(shè)計(jì)與分析>

貪心算法21ppt課件設(shè)[x1,...,xn]是最優(yōu)裝載問(wèn)題的一個(gè)滿足貪算法設(shè)計(jì)與分析>

貪心算法3.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法的正確性。算法的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為

O(nlogn)。22ppt課件算法設(shè)計(jì)與分析>貪心算法3.最優(yōu)子結(jié)構(gòu)性質(zhì)22ppt課件算法設(shè)計(jì)與分析>

貪心算法4.7多機(jī)調(diào)度問(wèn)題

[問(wèn)題描述]要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成，作業(yè)i所需時(shí)間為ti。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷，作業(yè)不能拆分成更小的子作業(yè)。該問(wèn)題是NP完全問(wèn)題，到目前為止還沒(méi)有有效的解法。用貪心選擇策略有時(shí)可設(shè)計(jì)出較好的近似算法。23ppt課件算法設(shè)計(jì)與分析>貪心算法4.7多機(jī)調(diào)度問(wèn)題 [問(wèn)[貪心近似算法]采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心策略.當(dāng)n≤m時(shí),只要將機(jī)器i的[0,ti]時(shí)間區(qū)間分配給作業(yè)i即可;當(dāng)n>m時(shí),將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序，然后依次將作業(yè)分配給空閑的處理機(jī)。算法設(shè)計(jì)與分析>

貪心算法24ppt課件[貪心近似算法]算法設(shè)計(jì)與分析>貪心算法24ppt課件算法設(shè)計(jì)與分析>

貪心算法classJobNode{friendvoidGreedy(JobNode*,int,int);friendvoidmain(void);public:operatorint()const{returntime;}private:intID,time;};classMachineNode{friendvoidGreedy(JobNode*,int,int);public:operatorint()const{returnavail;}private:intID,avail;}多機(jī)調(diào)度問(wèn)題的貪心近似算法作業(yè)結(jié)點(diǎn)類機(jī)器結(jié)點(diǎn)類25ppt課件算法設(shè)計(jì)與分析>貪心算法classJobNode{多template<classType>voidGreedy(Typea[]，intn，intm){if(n<=m){cont<<”為每個(gè)作業(yè)分配一臺(tái)機(jī)器.“<<endlreturn；}Sort(a，n)；//將作業(yè)按時(shí)間從大到小排序MinHeap<MachineNode>H(m)；MachineNodex；for(int

i=1；i<=m;i++){x．a(chǎn)vail=0；

x．ID=i;H．Insert(x)；}for(inti=n；i>=1；i--){

//作業(yè)分配過(guò)程H．DeleteMin(x)；//從堆中取出堆頂x機(jī)器

cout<<”將機(jī)器”<<x．ID<<“從”<<x．a(chǎn)vail<<"到”

<<(x．a(chǎn)vail十a(chǎn)[i]．time)<<”的時(shí)間段分配給作業(yè)”<<a[i].ID<<endl；

x．a(chǎn)vail+=a[i]．time；//機(jī)器的時(shí)間分配

H．insert(x)；}}

//重新插入,調(diào)整堆如果機(jī)器數(shù)大于作業(yè)數(shù)直接分配按照機(jī)器結(jié)點(diǎn)編號(hào)順序建立堆26ppt課件template<classType>如果機(jī)器數(shù)大于作業(yè)數(shù)算法設(shè)計(jì)與分析>

貪心算法時(shí)間復(fù)雜度分析n<=m時(shí)間O(1)n>m排序耗時(shí)O

(nlogn)

初始化堆O(m)

DeleteMin

和Insert耗時(shí)O

(nlogm)共需時(shí)間為：O

(nlogn+

nlog

m)=O(nlog

n)27ppt課件算法設(shè)計(jì)與分析>貪心算法時(shí)間復(fù)雜度分析27ppt課件第一章算法概述第二章遞歸與分治策略第三章動(dòng)態(tài)規(guī)劃第四章貪心算法第五章回朔法第六章分支限界法第七章隨機(jī)化算法算法設(shè)計(jì)與分析>目錄28ppt課件第一章算法概述第二章遞歸與分治策略第三章動(dòng)態(tài)規(guī)劃4.2貪心算法基本要素4.1活動(dòng)安排問(wèn)題4.3最優(yōu)裝載問(wèn)題算法設(shè)計(jì)與分析>目錄4.7多機(jī)調(diào)度問(wèn)題29ppt課件4.2貪心算法基本要素4.1活動(dòng)安排問(wèn)題4.3最優(yōu)裝載算法設(shè)計(jì)與分析>

貪心算法4.1活動(dòng)安排問(wèn)題有n個(gè)活動(dòng)E={1,2,…,n},其中每個(gè)活動(dòng)要使用同一資源,同一時(shí)間只允許一個(gè)活動(dòng)使用該資源.每個(gè)活動(dòng)i都有一個(gè)開始時(shí)間si,和一個(gè)結(jié)束時(shí)間fi.如果選擇活動(dòng)i,則它在時(shí)間區(qū)間[si,fi

)內(nèi)占用該資源;若區(qū)間[si,fi

)與[sj,fj

)不相交,則稱活動(dòng)i與j是相容的(兼容的).活動(dòng)安排問(wèn)題是要求在所給的活動(dòng)集合中選出最大相容活動(dòng)子集.30ppt課件算法設(shè)計(jì)與分析>貪心算法4.1活動(dòng)安排問(wèn)題有n個(gè)活動(dòng)E在安排時(shí)應(yīng)該將結(jié)束時(shí)間早的活動(dòng)盡量往前安排，好給后面的活動(dòng)安排留出更多的空間，從而達(dá)到安排最多活動(dòng)的目標(biāo)。貪心準(zhǔn)則應(yīng)當(dāng)是：在未安排的活動(dòng)中挑選結(jié)束時(shí)間最早的活動(dòng)安排。算法設(shè)計(jì)與分析>

貪心算法[直觀想法]31ppt課件在安排時(shí)應(yīng)該將結(jié)束時(shí)間早的活動(dòng)盡量往前安排，好給后面的活動(dòng)安算法設(shè)計(jì)與分析>

貪心算法[算法思路]1.將活動(dòng)按結(jié)束時(shí)間排序,得到活動(dòng)集E={e1,e2…en}；2.先將e1選入結(jié)果集合A中，即A={e1}；3.依次掃描每一個(gè)活動(dòng)ei:如果ei的si

>最后一個(gè)選入A的活動(dòng)ej的fj

,則將ei選入A中,否則放棄ei。32ppt課件算法設(shè)計(jì)與分析>貪心算法[算法思路]5ppt課件算法設(shè)計(jì)與分析>

貪心算法定理：考慮任意非空子問(wèn)題Sk，令am是Sk中結(jié)束時(shí)間最早的活動(dòng)，則am在Sk的某個(gè)最大兼容活動(dòng)子集中。證明：令A(yù)k是Sk的一個(gè)最大兼容活動(dòng)子集，且aj是Ak中結(jié)束時(shí)間最早的活動(dòng)。若aj=am，則證明am在Sk的某個(gè)最大兼容活動(dòng)子集中。若aj≠am，令集合,即將Ak中的aj替換am因?yàn)锳k中的活動(dòng)都是不相交的，aj是Ak中結(jié)束時(shí)間最早的活動(dòng)，而fm≤fj

，所以Ak′中的活動(dòng)都是不相交的。由于|

Ak′|=|

Ak|，因此得出結(jié)論Ak′也是Sk的一個(gè)最大活動(dòng)子集，且它包含am。33ppt課件算法設(shè)計(jì)與分析>貪心算法定理：考慮任意非空子問(wèn)題Sk，令2.最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。算法設(shè)計(jì)與分析>

貪心算法34ppt課件2.最優(yōu)子結(jié)構(gòu)性質(zhì)算法設(shè)計(jì)與分析>貪心算法7ppt課件3.貪心算法與動(dòng)態(tài)規(guī)劃算法的差異

算法設(shè)計(jì)與分析>

貪心算法相同點(diǎn)：都具有最優(yōu)子結(jié)構(gòu)性質(zhì)區(qū)別：動(dòng)態(tài)規(guī)劃法貪心算法選擇特征往往依賴于相關(guān)子問(wèn)題的解。只有解出相關(guān)子問(wèn)題才能作出選擇。當(dāng)前狀態(tài)下作出最好選擇，即局部最優(yōu)選擇，但不依賴于子問(wèn)題的解設(shè)計(jì)特征自底向上自頂向下35ppt課件3.貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 算法設(shè)計(jì)與分析>貪心算算法設(shè)計(jì)與分析>

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

給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

在選擇物品i裝入背包時(shí)，可以選擇物品i的部分，而不一定要全部裝入背包，1≤i≤n。不允許重復(fù)裝入。36ppt課件算法設(shè)計(jì)與分析>貪心算法背包問(wèn)題9ppt課件

于是，背包問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件，并使目標(biāo)函數(shù)達(dá)到最大的解向量X=(x1,x2,…,xn)。設(shè)xi表示物品i裝入背包的情況，根據(jù)問(wèn)題的要求，有如下約束條件和目標(biāo)函數(shù)：算法設(shè)計(jì)與分析>

貪心算法37ppt課件于是，背包問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件，并每次撿最輕的物品裝；每次撿價(jià)值最大的裝；每次裝包時(shí)既考慮物品的重量又考慮物品的價(jià)值，也就是說(shuō)每次撿單位價(jià)值最大的裝。算法設(shè)計(jì)與分析>

貪心算法貪心選擇：

只考慮到多裝些物品，但由于單位價(jià)值未必高，總價(jià)值不能達(dá)到最大；每次選擇的價(jià)值最大，但同時(shí)也可能占用了較大的空間，裝的物品少，未必能夠達(dá)到總價(jià)值最大確實(shí)能夠達(dá)到總價(jià)值最大。38ppt課件每次撿最輕的物品裝；算法設(shè)計(jì)與分析>貪心算法貪心選擇：首先計(jì)算每種物品單位重量的價(jià)值vi/wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略處理，直到背包裝滿為止。算法設(shè)計(jì)與分析>

貪心算法基本步驟：

39ppt課件首先計(jì)算每種物品單位重量的價(jià)值vi/wi，然后，依貪心選擇策算法設(shè)計(jì)與分析>

貪心算法voidKnapsack(intn,floatM,floatv[],floatw[],floatx[])//價(jià)值數(shù)組v[1:n]、重量數(shù)組w[1:n];

//它們?cè)氐呐帕许樞驖M足v[i]/w[i]≥v[i+1]/w[i+1];

//M是背包容量，x是解向量.

{floatc=M;

//使背包剩余容量初始化為M

int

i;Sort(n,v,w);

for(i=1;i<=n;i++)x[i]=0;//將解向量初始化為零

for(i=1;i<=n;i++){ifw[i]>cbreak;x[i]=1;c=c-w[i];}

if(

in)x[i]=c/w[i];}將各種物品依其單位重量的價(jià)值從大到小排序。算法的計(jì)算時(shí)間上界為O(nlogn)。40ppt課件算法設(shè)計(jì)與分析>貪心算法voidKnapsack(i0-1背包問(wèn)題：

給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。算法設(shè)計(jì)與分析>

貪心算法41ppt課件0-1背包問(wèn)題：在選擇裝入背包的物品時(shí)，對(duì)每種物品算法設(shè)計(jì)與分析>

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

42ppt課件算法設(shè)計(jì)與分析>貪心算法對(duì)于0-1背包問(wèn)題，貪心選擇之所算法設(shè)計(jì)與分析>

貪心算法4.3最優(yōu)裝載

有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為wi。最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。[問(wèn)題描述]滿足43ppt課件算法設(shè)計(jì)與分析>貪心算法4.3最優(yōu)裝載 1.算法描述

最優(yōu)裝載問(wèn)題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問(wèn)題的最優(yōu)解。算法設(shè)計(jì)與分析>

貪心算法44ppt課件1.算法描述算法設(shè)計(jì)與分析>貪心算法17ppt課件算法設(shè)計(jì)與分析>

貪心算法voidLoading(intx[],Typew[],floatc,intn){int*t=newint[n+1];Sort.(w,t,n);for(inti=0;i<n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}t[i]中存儲(chǔ)第i輕集裝箱在原來(lái)序列中的下標(biāo)x[i]記載第i個(gè)集裝箱是否裝入,x[i]=1裝入,x[i]=0未裝入45ppt課件算法設(shè)計(jì)與分析>貪心算法voidLoading(int物品重量分別為15，10，27，18，船載重為50定義：w[]={15,10,27,18}物品重量

T[]={1,0,3,2}物品從輕到重排序后序號(hào)

C=50船載重貪心算法計(jì)算步驟：

w[T[0]]=10<c,c=c-10=40

w[T[1]]=15<c,c=c-15=25

w[T[2]]=18<c,c=c-18=7

w[T[3]]=27>c算法設(shè)計(jì)與分析>

貪心算法[例]46ppt課件物品重量分別為15，10，27，18，船載重為50算法設(shè)計(jì)與算法設(shè)計(jì)與分析>

貪心算法2.貪心選擇性質(zhì)設(shè)貨箱已經(jīng)從小到大排序，是最優(yōu)裝載問(wèn)題的一個(gè)最優(yōu)解，又設(shè)如果給定的最優(yōu)裝載問(wèn)題有解，則1≤k≤n（1）當(dāng)k=1時(shí)，是一個(gè)滿足貪婪選擇性質(zhì)的最優(yōu)解。（2）當(dāng)k>1時(shí)，則因此，所給最優(yōu)裝載問(wèn)題的一個(gè)可行解，且是最優(yōu)解。

47ppt課件算法設(shè)計(jì)與分析>貪心算法2.貪心選擇性質(zhì)設(shè)貨箱已經(jīng)從小到設(shè)[x1,...,xn

]是最優(yōu)裝載問(wèn)題的一個(gè)滿足貪心選擇性質(zhì)的最優(yōu)解，則x1=1時(shí),[x2,...,xn

]是輪船載重量為c-w1且待裝集裝箱為{2,...,n}時(shí)相應(yīng)最優(yōu)裝載問(wèn)題的一個(gè)最優(yōu)解。算法設(shè)計(jì)與分析>

貪心算法48ppt課件設(shè)[x1,...,xn]是最優(yōu)裝載問(wèn)題的一個(gè)滿足貪算法設(shè)計(jì)與分析>

貪心算法3.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法的正確性。算法的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為

O(nlogn)。49ppt課件算法設(shè)計(jì)與分析>貪心算法3.最優(yōu)子結(jié)構(gòu)性質(zhì)22ppt課件算法設(shè)計(jì)與分析>

貪心算法4.7多機(jī)調(diào)度問(wèn)題

[問(wèn)題描述]要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成，作業(yè)i所需時(shí)間為ti。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷，作業(yè)不能拆分成更小的子作業(yè)。該問(wèn)題是NP完全問(wèn)題，到目前為止還沒(méi)有有效的解法。用貪心選擇策略有時(shí)可設(shè)計(jì)出較好的近似算法。50ppt課件算法設(shè)計(jì)與分析>貪心算法4.7多機(jī)調(diào)度問(wèn)題 [問(wèn)[貪心近似算法]采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心策略.當(dāng)n≤m時(shí),只要將機(jī)器i的[0,ti]時(shí)間區(qū)間分配給作業(yè)i即可;當(dāng)n>m時(shí),將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序，然后依次將作業(yè)分配給空閑的處理機(jī)。算法設(shè)計(jì)與分析>

貪心算法51ppt課件