Cc語(yǔ)言貪心算法學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1Cc語(yǔ)言貪心算法語(yǔ)言貪心算法貪心算法第1頁(yè)/共15頁(yè)2 2、基本思路、基本思路(1)建立數(shù)學(xué)模型來(lái)描述問(wèn)題。(2)把求解的問(wèn)題分成若干個(gè)子問(wèn)題。(3)對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。(4)把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解。3 3、算法實(shí)現(xiàn)。、算法實(shí)現(xiàn)。(1)從問(wèn)題的某個(gè)初始解出發(fā)。(2)采用循環(huán)語(yǔ)句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局部最優(yōu)策略，得到一個(gè)部分解，縮小問(wèn)題的范圍或規(guī)模。(3)將所有部分解綜合起來(lái)，得到問(wèn)題的最終解。第2頁(yè)/共15頁(yè)例題例題1、背包問(wèn)題背包問(wèn)題 有一個(gè)背包，背包容量是有一個(gè)背包，背包容量是M=150。有。有7個(gè)物品，物品可以分割成任意

2、大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘?。個(gè)物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘俊?物品物品 ：A B C D E F G 重量重量 ：35 30 60 50 40 10 25 價(jià)值價(jià)值 ：10 40 30 50 35 40 30 分析：分析：目標(biāo)函數(shù)：目標(biāo)函數(shù)： pi最大最大約束條件是裝入的物品總重量不超過(guò)背包容量：約束條件是裝入的物品總重量不超過(guò)背包容量：wi=M( M=150) （1）根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？）根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最

3、優(yōu)？（2）每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？）每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？（3）每次選取單位容量?jī)r(jià)值最大的物品，成為解本題的策略。）每次選取單位容量?jī)r(jià)值最大的物品，成為解本題的策略。 根據(jù)以上的分析我們就可以得到解決本題的策略。即單位容量最大的物品。根據(jù)以上的分析我們就可以得到解決本題的策略。即單位容量最大的物品。第3頁(yè)/共15頁(yè)例題例題1算法實(shí)現(xiàn)：算法實(shí)現(xiàn)： 在算法的實(shí)現(xiàn)上應(yīng)該不是很難，只要我們算出每個(gè)物品在單位容量上的價(jià)值就行，然后再使用一個(gè)排序的算法，將其從大到小排序。然后再根據(jù)背包當(dāng)前剩下的容量來(lái)選取本次物品的重量。如果背包的容量比當(dāng)前武平的容量要大，

4、那么就將當(dāng)前物品全部裝進(jìn)去。如果不夠，那么就將當(dāng)前物品切割裝進(jìn)去。然后就可以跳出循環(huán)。這里我們?cè)诖鎯?chǔ)數(shù)據(jù)時(shí)為了方便起見(jiàn)可以使用一個(gè)結(jié)構(gòu)體的方式來(lái)存儲(chǔ)。結(jié)構(gòu)體里面保存物品的重量，價(jià)值，以及單位質(zhì)量的價(jià)值。然后使用在算法的實(shí)現(xiàn)上應(yīng)該不是很難，只要我們算出每個(gè)物品在單位容量上的價(jià)值就行，然后再使用一個(gè)排序的算法，將其從大到小排序。然后再根據(jù)背包當(dāng)前剩下的容量來(lái)選取本次物品的重量。如果背包的容量比當(dāng)前武平的容量要大，那么就將當(dāng)前物品全部裝進(jìn)去。如果不夠，那么就將當(dāng)前物品切割裝進(jìn)去。然后就可以跳出循環(huán)。這里我們?cè)诖鎯?chǔ)數(shù)據(jù)時(shí)為了方便起見(jiàn)可以使用一個(gè)結(jié)構(gòu)體的方式來(lái)存儲(chǔ)。結(jié)構(gòu)體里面保存物品的重量，價(jià)值，以及單

5、位質(zhì)量的價(jià)值。然后使用sort函數(shù)來(lái)排序，排序時(shí)我們只要重寫函數(shù)來(lái)排序，排序時(shí)我們只要重寫sort函數(shù)里面的比較函數(shù)即可。函數(shù)里面的比較函數(shù)即可。Sort(p,p+n,Up)。P使我們保存物品的結(jié)構(gòu)體。使我們保存物品的結(jié)構(gòu)體。N是物品的總數(shù)。是物品的總數(shù)。Up使我們自定義的排序方法。使我們自定義的排序方法。第4頁(yè)/共15頁(yè)第5頁(yè)/共15頁(yè)例題例題2：活動(dòng)安排：活動(dòng)安排題目：題目： 設(shè)有設(shè)有n個(gè)活動(dòng)的集合個(gè)活動(dòng)的集合E=1,2,n，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)

6、活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間和一個(gè)結(jié)束時(shí)間fi,且且si fi 。要求設(shè)計(jì)程序，使得安排的活動(dòng)最多。要求設(shè)計(jì)程序，使得安排的活動(dòng)最多。分析：分析： 活動(dòng)安排問(wèn)題要求安排一系列爭(zhēng)用某一公共資源的活動(dòng)。用貪心算法可提供一個(gè)簡(jiǎn)單、漂亮的方法，使盡可能多的活動(dòng)能兼容的使用公共資源。設(shè)有活動(dòng)安排問(wèn)題要求安排一系列爭(zhēng)用某一公共資源的活動(dòng)。用貪心算法可提供一個(gè)簡(jiǎn)單、漂亮的方法，使盡可能多的活動(dòng)能兼容的使用公共資源。設(shè)有n個(gè)活動(dòng)的集合個(gè)活動(dòng)的集合0，1，2，n-1，其中每個(gè)活動(dòng)都要求使用同一資源，如會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)，其中每個(gè)活動(dòng)都要求使用同一資源，如會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間都有一個(gè)要求使用該資源的起始時(shí)間starti和一個(gè)結(jié)束時(shí)間和一個(gè)結(jié)束時(shí)間endi，且，且startij的部分。的部分。演示算法實(shí)現(xiàn)過(guò)程。演示算法實(shí)現(xiàn)過(guò)程。第8頁(yè)/共15頁(yè)12345