C++c語言貪心算法ppt課件

1、本次課程的主要內(nèi)容本次課程的主要內(nèi)容貪心算法貪心算法貪心算法1 1、什么是貪心算法、什么是貪心算法: :貪心算法又稱貪婪算法是指，在對問題求解時(shí)，總是做出貪心算法又稱貪婪算法是指，在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。優(yōu)解或

2、者是整體最優(yōu)解的近似解。 2 2、基本思路、基本思路(1)(1)建立數(shù)學(xué)模型來描述問題。建立數(shù)學(xué)模型來描述問題。 (2) (2)把求解的問題分成若干個(gè)子問題。把求解的問題分成若干個(gè)子問題。 (3) (3)對每一子問題求解，得到子問題的局部最優(yōu)解。對每一子問題求解，得到子問題的局部最優(yōu)解。 (4) (4)把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。 3 3、算法實(shí)現(xiàn)。、算法實(shí)現(xiàn)。(1)(1)從問題的某個(gè)初始解出發(fā)。從問題的某個(gè)初始解出發(fā)。(2)(2)采用循環(huán)語句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局部最優(yōu)采用循環(huán)語句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時(shí)，就

3、根據(jù)局部最優(yōu)策略，得到一個(gè)部分解，縮小問題的范圍或規(guī)模。策略，得到一個(gè)部分解，縮小問題的范圍或規(guī)模。(3)(3)將所有部分解綜合起來，得到問題的最終解。將所有部分解綜合起來，得到問題的最終解。貪心算法貪心算法-例題分析例題分析例題例題1、背包問題背包問題 有一個(gè)背包，背包容量是有一個(gè)背包，背包容量是M=150。有。有7個(gè)物品，物品可以分割成任意大小。要個(gè)物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?cè)萘?。求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?cè)萘俊?物品物品 ：A B C D E F G 分量分量 ：35 30 60 50 40 10 25 價(jià)值

4、價(jià)值 ：10 40 30 50 35 40 30 分析：分析：目標(biāo)函數(shù)：目標(biāo)函數(shù)： pi最大最大約束條件是裝入的物品總重量不超過背包容量：約束條件是裝入的物品總重量不超過背包容量：wi=M( M=150) （1根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？（2每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？（3每次選取單位容量價(jià)值最大的物品，成為解本題的策略。每次選取單位容量價(jià)值最大的物品，成為解本題的策略。 根據(jù)以上的分析我們就可以得到解決本題的策略。即單

5、位容量最大的物品。根據(jù)以上的分析我們就可以得到解決本題的策略。即單位容量最大的物品。貪心算法貪心算法-例題分析例題分析例題例題1算法實(shí)現(xiàn)：算法實(shí)現(xiàn)： 在算法的實(shí)現(xiàn)上應(yīng)該不是很難，只要我們算出每個(gè)物品在單位容量上的價(jià)值在算法的實(shí)現(xiàn)上應(yīng)該不是很難，只要我們算出每個(gè)物品在單位容量上的價(jià)值就行，然后再使用一個(gè)排序的算法，將其從大到小排序。然后再根據(jù)背包當(dāng)前剩就行，然后再使用一個(gè)排序的算法，將其從大到小排序。然后再根據(jù)背包當(dāng)前剩下的容量來選取本次物品的重量。如果背包的容量比當(dāng)前武平的容量要大，那么下的容量來選取本次物品的重量。如果背包的容量比當(dāng)前武平的容量要大，那么就將當(dāng)前物品全部裝進(jìn)去。如果不夠，那么

6、就將當(dāng)前物品切割裝進(jìn)去。然后就可就將當(dāng)前物品全部裝進(jìn)去。如果不夠，那么就將當(dāng)前物品切割裝進(jìn)去。然后就可以跳出循環(huán)。這里我們在存儲數(shù)據(jù)時(shí)為了方便起見可以使用一個(gè)結(jié)構(gòu)體的方式來以跳出循環(huán)。這里我們在存儲數(shù)據(jù)時(shí)為了方便起見可以使用一個(gè)結(jié)構(gòu)體的方式來存儲。結(jié)構(gòu)體里面保存物品的重量，價(jià)值，以及單位質(zhì)量的價(jià)值。然后使用存儲。結(jié)構(gòu)體里面保存物品的重量，價(jià)值，以及單位質(zhì)量的價(jià)值。然后使用sort函數(shù)來排序，排序時(shí)我們只要重寫函數(shù)來排序，排序時(shí)我們只要重寫sort函數(shù)里面的比較函數(shù)即可。函數(shù)里面的比較函數(shù)即可。Sort(p,p+n,Up)。P使我們保存物品的結(jié)構(gòu)體。使我們保存物品的結(jié)構(gòu)體。N是物品的總數(shù)。是物品

7、的總數(shù)。Up使我們自定使我們自定義的排序方法。義的排序方法。貪心算法貪心算法-例題例題1代碼代碼貪心算法貪心算法-例題分析例題分析例題例題2：活動安排：活動安排標(biāo)題：標(biāo)題： 設(shè)有設(shè)有n個(gè)活動的集合個(gè)活動的集合E=1,2,n，其中每個(gè)活動都要求使用同一資源，如演講，其中每個(gè)活動都要求使用同一資源，如演講會場等，而在同一時(shí)間內(nèi)只有一個(gè)活動能使用這一資源。每個(gè)活動會場等，而在同一時(shí)間內(nèi)只有一個(gè)活動能使用這一資源。每個(gè)活動i都有一個(gè)要求使都有一個(gè)要求使用該資源的起始時(shí)間用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間和一個(gè)結(jié)束時(shí)間fi,且且si fi 。要求設(shè)計(jì)程序，使得安排的活動。要求設(shè)計(jì)程序，使得安排的活動最

8、多。最多。分析：分析： 活動安排問題要求安排一系列爭用某一公共資源的活動。用貪心算法可提供一活動安排問題要求安排一系列爭用某一公共資源的活動。用貪心算法可提供一個(gè)簡單、漂亮的方法，使盡可能多的活動能兼容的使用公共資源。設(shè)有個(gè)簡單、漂亮的方法，使盡可能多的活動能兼容的使用公共資源。設(shè)有n個(gè)活動的集個(gè)活動的集合合0，1，2，n-1，其中每個(gè)活動都要求使用同一資源，如會場等，而在同，其中每個(gè)活動都要求使用同一資源，如會場等，而在同一時(shí)間內(nèi)只有一個(gè)活動能使用這一資源。每個(gè)活動一時(shí)間內(nèi)只有一個(gè)活動能使用這一資源。每個(gè)活動i都有一個(gè)要求使用該資源的起始都有一個(gè)要求使用該資源的起始時(shí)間時(shí)間starti和一個(gè)

9、結(jié)束時(shí)間和一個(gè)結(jié)束時(shí)間endi，且，且startij的部分。的部分。演示算法實(shí)現(xiàn)過程。演示算法實(shí)現(xiàn)過程。人工模擬人工模擬1234555666最小生成樹的耗費(fèi)為最小生成樹的耗費(fèi)為15算法難點(diǎn)算法難點(diǎn)從剛才的演示過程，可知算法實(shí)現(xiàn)有兩個(gè)難點(diǎn)：（1邊的選擇要求從小到大選擇，則開始顯然要對邊進(jìn)行升序排序。（2選擇的邊是否需要，則從判斷該邊加入后是否構(gòu)成環(huán)入手。難點(diǎn)解決一）難點(diǎn)解決一）（1 1對邊升序排序?qū)吷蚺判?方法可根據(jù)以前方法可根據(jù)以前 中選擇合適的排序。中選擇合適的排序。 在此采用鏈?zhǔn)浇Y(jié)構(gòu)，通過插入排序完成。在此采用鏈?zhǔn)浇Y(jié)構(gòu)，通過插入排序完成。 每一結(jié)點(diǎn)存放一條邊的左右端點(diǎn)序號、權(quán)值及后繼結(jié)點(diǎn)指針。每一結(jié)點(diǎn)存放一條邊的左右端點(diǎn)序號、權(quán)值及后繼結(jié)點(diǎn)指針。難點(diǎn)解決二）難點(diǎn)解決二）（2 2邊的加入是否構(gòu)成環(huán)邊的加入是否構(gòu)成環(huán) 一開始假定各頂點(diǎn)分別為一組，其組號為端點(diǎn)序號。一開始假定各頂點(diǎn)分別為一組，其組號為端點(diǎn)序號。 選擇某邊后，看其兩個(gè)端點(diǎn)是否在同一組中，即所在組號是否相同選擇某邊后，看其