貪心算法詳解與應(yīng)用舉例班級：軟件12-1組長：孟潔組員：王明桃趙強10/6/20231

※詳解：

算法思想

算法過程

算法分析

※應(yīng)用舉例：

常見應(yīng)用10/6/20232?算法思想找錢的方法：25+25+10+5+1+1我們有種直覺的傾向：

在找零錢時，直覺告訴我們使用面值大的硬幣，剩余的金額就越少。

假設(shè)提供了數(shù)目不限的面值為25美分、10美分、5美分、及1美分的硬幣。假設(shè)一個小孩買了33美分的糖果（需要找給小孩67美分）。引例——找零錢10/6/20233?算法思想

在現(xiàn)實生活中，我們經(jīng)常為下意識的做貪心的選擇，例如在購買商品時候總是尋求物美價廉的物品，在質(zhì)量相同情況下，價格低的首選。

10/6/20234?算法思想

將問題的求解過程看作是一系列選擇，每次選擇一個輸入，每次選擇都是當前狀態(tài)下的最好選擇(局部最優(yōu)解)。每作一次選擇后，所求問題會簡化為一個規(guī)模更小的子問題。從而通過每一步的最優(yōu)解逐步達到整體的最優(yōu)解。10/6/20235?算法過程顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。找的硬幣總數(shù)最少→使剩余金額最少找硬幣的時候：【標準轉(zhuǎn)化】貪心猜想（貪心策略）原現(xiàn)10/6/20236?算法過程[貪心算法步驟]從問題的某一初始解出發(fā)；

while

能朝給定總目標前進一步

do

求出可行解的一個解元素；

由所有解元素組合成問題的一個可行解；真正意義要求解原問題將原問題變成更小子問題的步驟理解10/6/20237?算法過程

【貪心算法一般步驟】1、設(shè)計數(shù)據(jù)找規(guī)律2、進行貪心猜想3、正確性證明（嚴格證明和一般證明）·嚴格證明：數(shù)學(xué)歸納和反證法·一般證明：列舉反例4、程序?qū)崿F(xiàn)}若無法證明，此證明可省10/6/20238?算法分析【適用問題】具備貪心選擇和最優(yōu)子結(jié)構(gòu)性質(zhì)的最優(yōu)化問題【常見應(yīng)用】背包問題,最小生成樹,最短路徑,作業(yè)調(diào)度等等【算法優(yōu)點】求解速度快,時間復(fù)雜性有較低的階.【算法缺點】需證明是最優(yōu)解.整體的最優(yōu)解可通過一系列局部最優(yōu)解達到.每次的選擇可以依賴以前作出的選擇,但不能依賴于后面的選擇問題的整體最優(yōu)解中包含著它子問題的最優(yōu)解10/6/20239?常見應(yīng)用1、活動安排問題【問題陳述】設(shè)有n個活動E={1,2,…,n}要使用同一資源,同一時間內(nèi)只允許一個活動使用該資源.設(shè)活動i的起止時間區(qū)間[si,fi),如果選擇了活動i,則它在時間區(qū)間[si,fi)內(nèi)占用該資源;若[si,fi)與[sJ,fJ)不相交,則稱活動i與j是相容的.求解目標是在所給的活動集合中選出最大相容活動子集.【算法思路】將n個活動按結(jié)束時間非減序排列,依次考慮活動i,若i與已選擇的活動相容,則添加此活動到相容活動子集.【例】設(shè)待安排的11個活動起止時間按結(jié)束時間的非減序排列事件編號1234567891011發(fā)生時刻130535688212結(jié)束時刻456789101112131410/6/202310?常見應(yīng)用

活動安排問題貪心算法：voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}10/6/202311?常見應(yīng)用2、多機調(diào)度問題

多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。

約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。例如，設(shè)7個獨立作業(yè){1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業(yè)所需時間為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時間為17。采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計出解多機調(diào)度問題的較好的近似算法。1410/6/202312

?常見應(yīng)用

3、排隊問題

在一個醫(yī)院B超室，有n個人要做不同身體部位的B超，已知每個人需要處理的時間為ti，（0<i<=n）,請求出一種排列次序，使每個人排隊等候時間總和最小。本題貪心算法：

n個人時間從小到大排序，就是這n個人最佳排隊方案。求部分和的和即為所求。10/6/202313談?wù)勛约旱南敕ā?0/6/202314選擇需慎重

貪心算法在對問題求解時，總是作出在當前看來是最好的選擇。也就是說，不從整體上加以考慮，它所作出的僅僅是在某種意義上的局部最優(yōu)解。eg：數(shù)字三角形問題：有一個數(shù)字三角形（如下圖）?，F(xiàn)有一只螞蟻從頂層開始向下走，每走下一級時，可向左下方向或右下方向走。求走到底層后它所經(jīng)過的數(shù)的最大值。解：如果用貪心法，每次向最大的方向

走，得到結(jié)果為1+6+8+2+3=20?？墒敲髅鬟€有另一條路，1+3+6+6+7=23。問題出在哪？每次的選擇對后面的步驟會有影響！第三級選了8，就選不到第四、五級較大的數(shù)了。

16382621653247610/6/202315綜述

貪心算法是一種分級處理方法，它得到某種度量意義下一個問題的最優(yōu)解，所做的每一次選擇都是當前狀態(tài)下的貪心選擇，通過一系列的選擇來得到最終解。這種策略是一種很簡潔的方法，適用于許多問題，但并不能依賴于它，因為它還有一下不足：（1）不能保證求得的最后解是最佳的，由于貪心策略總是從局部看來是最優(yōu)