lab5-貪心算法設(shè)計(jì)與應(yīng)用

1、實(shí)驗(yàn)五實(shí)驗(yàn)五貪心算法設(shè)計(jì)與應(yīng)用貪心算法設(shè)計(jì)與應(yīng)用一基本原理的概括一基本原理的概括貪心法是一種算法設(shè)計(jì)技術(shù)，通常用于求解最優(yōu)化問題。通過(guò)一系列選擇步驟來(lái)構(gòu)造問題的解，每一步都是對(duì)當(dāng)前部分解的一個(gè)擴(kuò)展，直至獲得問題的完整解。所做的每一步選擇都必須滿足：1）可行的：必須滿足問題的約束。2）局部最優(yōu)：當(dāng)前所有可能的選擇中最佳的局部選擇。3）不可取消:選擇一旦做出，在后面的步驟中就無(wú)法改變了。要注意的是，貪心法不能保證總能得到最優(yōu)解（一系列的局部

2、最優(yōu)選擇不能保證最后得到整體最優(yōu)解）二該類算法設(shè)計(jì)與實(shí)現(xiàn)的要點(diǎn)二該類算法設(shè)計(jì)與實(shí)現(xiàn)的要點(diǎn)貪心算法往往效率高，一般時(shí)間復(fù)雜性為多項(xiàng)式階。貪心算法一般較簡(jiǎn)單，其關(guān)鍵和難點(diǎn)在于貪心選擇策略的確定，以及證明相應(yīng)的貪心算法確實(shí)可求出最優(yōu)解。三實(shí)驗(yàn)?zāi)康暮鸵笕龑?shí)驗(yàn)?zāi)康暮鸵罄斫庳澬乃惴ǖ幕驹恚莆肇澬乃惴ㄔO(shè)計(jì)的基本方法及其應(yīng)用；四實(shí)驗(yàn)內(nèi)容四實(shí)驗(yàn)內(nèi)容(一)加油問題（加油問題（ProblemSet1702）：）：1.1.問題描述問題描述一個(gè)旅行家想

3、駕駛汽車從城市A到城市B（設(shè)出發(fā)時(shí)油箱是空的）。給定兩個(gè)城市之間的距離dis、汽車油箱的容量c、每升汽油能行駛的距離d、沿途油站數(shù)n、油站i離出發(fā)點(diǎn)的距離d[i]以及該站每升汽油的價(jià)格p[i]i=12…n。設(shè)d[1]=0#defineMAX20voidlook(floatdis[]floatpir[]intnintd2intoil)dis距離起點(diǎn)距離，距離起點(diǎn)距離，pir油價(jià)油價(jià)intijkfloatpirce=0.0c1=0xc2f(