ACM程序設12021/8/5計計算機學院劉春英調課三周(11/6,11/13,11/20)22021/8/5今天，你了嗎？32021/8/5每周一星（5）：楓冰葉子42021/8/5第六講52021/8/5貪心算法（Greedy

Algorithm）還記得hdoj_1009嗎？62021/8/5FatMouse'

Trade所謂“貪心算法”是指：72021/8/5在對問題求解時，總是作出在當前看來是最好的選擇。也就是說，不從整體上加以考慮，它所作出的僅僅是在某種意義上的局部最優(yōu)解（是否是全局最優(yōu)，需要證明）。特別說明：82021/8/5若要用貪心算法求解某問題的整體最優(yōu)解，必須首先證明貪心思想在該問題的應用結果就是最優(yōu)解??！用事實說話——92021/8/5實例分析102021/8/5一、事件序列問題112021/8/5已知N個事件的發(fā)生時刻和結束時刻（見下表，表中事件已按結束時刻升序排序）。一些在時間上沒有重疊的事件，可以構成一個事件序列，如事件{2，8，10}。事件序列包含的事件數(shù)目，稱為該事件序列的長度。請編程找出一個最長的事件序列。事件編號01234567891011發(fā)生時刻130325641081515結束時刻3478910121415181920算法分析：122021/8/5不妨用Begin[i]和End[i]表示事件i的開始時刻和結束時刻。則原題的要求就是找一個最長的序列a1<a2<…<an，滿足：Begin[a1]<End[a1]<=…<=

Begin[an]<End[an]可以證明，如果在可能的事件a1<a2<…<an中選取在時間上不重疊的最長序列，那么一定存在一個包含a1（結束最早）的最長序列。（證明：略）思考：132021/8/5請談談自己的解題思路練習題目：2037今年暑假不AC142021/8/5二、區(qū)間覆蓋問題用i來表示x軸上坐標為[i-1,i]的區(qū)間（長度為1），并給出M(1=<M=<200)個不同的整數(shù)，表示M個這樣的區(qū)間?，F(xiàn)在讓你畫幾條線段覆蓋住所有的區(qū)間，條件是：每條線段可以任意長，但是要求所畫線段之和最小，并且線段的數(shù)目不超過N(1=<N=<50)。例如：M=5個整數(shù)1、3、4、8和11表示區(qū)間，要求所用線段不超過N=3條0

1

2

3

4

5

6

7

8

9

10

11152021/8/5算法分析：162021/8/5如果N>=M，那么顯然用M條長度為1的線段可以覆蓋住所有的區(qū)間，所求的線段總長為M。如果N=1，那么顯然所需線段總長為：…如果N=2，相當于N=1的情況下從某處斷開（從哪兒斷開呢？）。如果N=k呢？三、HDOJ_1050

Moving

Tables172021/8/5題目鏈接Sample

Input3410

2030

4050

6070

8021

32

200310

10020

8030

50Sample

Output102030算法分析：182021/8/51、如果沒有交叉，總時間應該是多少？2、影響搬運時間的因素是什么？3、如果每趟處理都包含最大重疊，處理后的效果是什么？4、得出什么結論？HDOJ_1050源碼：192021/8/5#include

<iostream>using

namespace

std;int

main(){

int

t,i,j,N,P[200];int

s,d,temp,k,min;cin>>t;for(i=0;i<t;i++){for(j=0;j<200;j++)P[j]=0;cin>>N;for(j=0;j<N;j++){cin>>s>>d;s=(s-1)/2;d=(d-1)/2;if(s>d){

temp=s;s=d;d=temp;

}for(k=s;k<=d;k++)P[k]++;}min=-1;for(j=0;j<200;j++)if(P[j]>min)min=P[j];cout<<min*10<<endl;}return

0;}貪心算法的基本步驟202021/8/51、從問題的某個初始解出發(fā)。2、采用循環(huán)語句，當可以向求解目標前進一步時，就根據(jù)局部最優(yōu)策略，得到一個部分解，縮小問題的范圍或規(guī)模。3、將所有部分解綜合起來，得到問題的最終解。貪心算法都很簡單嗎？212021/8/5看一道難一些的。（2004年上海賽區(qū)試題：當時算是簡單題）ACM-ICPC

Asia

Regional,2004,

Shanghai222021/8/5Problem

HTian

Ji—The

Horse

Racing示意圖：9283717487957174879592

-200

83

-200

-200928371748795-200232021/8/5+200+200談談自己的想法——242021/8/5Case1:252021/8/5King:200180160Tianji:190170150Case2:262021/8/5King:200180160Tianji:180170150Case3:272021/8/5King:200180160Tianji:180155150總體的思路是什么？282021/8/5提醒：292021/8/5很多貪心類型的題目都象本

題一樣，不是最樸素的貪心，而是需要做一些變化，對于

我們，關鍵是找到貪心的本

質！本講重點：(連通網的)最小生成樹302021/8/5假設要在n個城市之間建立通訊聯(lián)絡網，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經費的前提下建立這個通訊網？312021/8/5問題：該問題等價于：構造網的一棵最小生成樹，即：在e條帶權的邊中選取n-1

條邊（不構成回路），使“權值之和”為最小。算法一：（普里姆算法）算法二：（克魯斯卡爾算法）322021/8/5MST性質：332021/8/5假設N={V,{E}}是一個連通網，U是頂點集V的一個非空子集。若（u,v）是一條具有最小權值的邊，其中u∈U,v∈V-U,則必定存在一棵包含邊（u,v）的最小生成樹。證明（略）。取圖中任意一個頂點v

作為生成樹的根，之后往生成樹上添加新的頂點w。在添加的頂點w和已經在生成樹上的頂點v

之間必定存在一條邊，并且該邊的權值在所有連通頂點v

和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點，直至生成樹上含有n-1個頂點為止。342021/8/5普里姆算法的基本思想:例如:191827ae12dcbgf2021/8/57148531621所得生成樹權值和=

14+8+3+5+16+21

=

6735一般情況下所添加的頂點應滿足下列條件:在生成樹的構造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U

和尚未落在生成樹上的頂點集V-U，則應在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。362021/8/5g19514181627821a12ec3b7dclosedgef0

1

2

3

4

5

6AdjvexLowcosta19141814例如:ae123d21

16c

d

e

a

d

e755

3

8372021/8/5考慮問題的出發(fā)點:為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能地小。具體做法:先構造一個只含n

個頂點的子圖

SG，然后從權值最小的邊開始，若它的添加不使SG

中產生回路，則在SG

上加上這條邊，如此重復，直至加上n-1條邊為止。382021/8/5克魯斯卡爾算法的基本思想：27edcgf148531621例如:7392021/8/51218a

19

b普里姆算法

克魯斯卡爾算法時間復雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應范圍比較兩種算法402021/8/5請務必寫出自己的模版！412021/8/5再次提醒:調課三周(11/6,11/13,11/20)422021/8/5附：貪心算法練習題：432021/8/51045

Fire

Net1050

Moving

Tables1051

Wood