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

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

2、大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?cè)萘俊€物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?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最大最大約束條件是裝入的物品總重量不超過背包容量：約束條件是裝入的物品總重量不超過背包容量：wi=M( M=150) （1）根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？）根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最

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

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

5、位質(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ù)。是物品的總數(shù)。Up使我們自定義的排序方法。使我們自定義的排序方法。第4頁/共15頁第5頁/共15頁例題例題2：活動安排：活動安排題目：題目： 設(shè)有設(shè)有n個活動的集合個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時(shí)間內(nèi)只有一個活動能使用這一資源。每個活動，其中每個活動都要求使用同一資源，如演講會場等，而在同一時(shí)間內(nèi)只有一個

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