1、實(shí)驗(yàn)二,貪心算法應(yīng)用實(shí)驗(yàn),一、實(shí)驗(yàn)?zāi)康?1. 運(yùn)用背包問(wèn)題解決具體問(wèn)題 2. 培養(yǎng)編程與上機(jī)調(diào)試能力,二、實(shí)驗(yàn)內(nèi)容,實(shí)現(xiàn)背包問(wèn)題的貪心算法 己知一個(gè)容量為M的背包?，F(xiàn)在要從n種物品中選取若干裝入背包中，每種物品的重量為w(i) 、價(jià)值為p(i) 。定義一種可行的背包裝載為：背包中物品的總重量不能超過(guò)背包的容量，每種物品僅有一件，可以選擇放或不放。采取怎樣的裝包方案才會(huì)使裝入背包的物品價(jià)值總和最大? 考慮：如果物品可分割，算法如何實(shí)現(xiàn)（選做）。,三、實(shí)驗(yàn)原理,貪心算法是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇，不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解。 貪心算法(G

2、reedy algorithm)是一種對(duì)某些求最優(yōu)解問(wèn)題的更簡(jiǎn)單、更迅速的設(shè)計(jì)技術(shù)。它采用自頂向下,以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題, 通過(guò)每一步貪心選擇，可得到問(wèn)題的一個(gè)最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，所以貪婪法不要回溯。,三、實(shí)驗(yàn)原理,貪心算法的基本思路 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è)解。,三、實(shí)驗(yàn)原理,算法的實(shí)現(xiàn)過(guò)程 從問(wèn)題的某一個(gè)初始解出發(fā)，逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。由所有解元素組合成問(wèn)題的一個(gè)可行解。 該算法存在問(wèn)題： 1、不能保證求得的最后解是最佳的； 2、不能用來(lái)求最大或最小解問(wèn)題； 3、只能求滿足某些約束條件的可行解的范圍。,四、實(shí)驗(yàn)步驟,1、設(shè)計(jì)算法； 2、采用高級(jí)語(yǔ)言實(shí)現(xiàn)該算法； 3、調(diào)試程序，檢查輸出結(jié)果。,編程環(huán)境,C語(yǔ)言編程平臺(tái)Turbo C 程序集成環(huán)境或 Visual C+