acm程序設(shè)計(jì)課件貪心算法

2023/1/91ACM程序設(shè)計(jì)計(jì)算機(jī)學(xué)院劉春英2023/1/92調(diào)課三周(11/6,11/13,11/20)2023/1/93今天，你了嗎？AC2023/1/94每周一星（5）：楓冰葉子

2023/1/95第六講貪心算法（GreedyAlgorithm）2023/1/96還記得hdoj_1009嗎？FatMouse'Trade2023/1/97所謂“貪心算法”是指：

在對(duì)問題求解時(shí)，總是作出在當(dāng)前看來是最好的選擇。也就是說，不從整體上加以考慮，它所作出的僅僅是在某種意義上的局部最優(yōu)解（是否是全局最優(yōu)，需要證明）。2023/1/98特別說明：

若要用貪心算法求解某問題的整體最優(yōu)解，必須首先證明貪心思想在該問題的應(yīng)用結(jié)果就是最優(yōu)解??！2023/1/99用事實(shí)說話——2023/1/910實(shí)例分析2023/1/911一、事件序列問題

已知N個(gè)事件的發(fā)生時(shí)刻和結(jié)束時(shí)刻（見下表，表中事件已按結(jié)束時(shí)刻升序排序）。一些在時(shí)間上沒有重疊的事件，可以構(gòu)成一個(gè)事件序列，如事件{2，8，10}。事件序列包含的事件數(shù)目，稱為該事件序列的長(zhǎng)度。請(qǐng)編程找出一個(gè)最長(zhǎng)的事件序列。事件編號(hào)01234567891011發(fā)生時(shí)刻130325641081515結(jié)束時(shí)刻34789101214151819202023/1/912算法分析：不妨用Begin[i]和End[i]表示事件i的開始時(shí)刻和結(jié)束時(shí)刻。則原題的要求就是找一個(gè)最長(zhǎng)的序列a1<a2<…<an，滿足：Begin[a1]<End[a1]<=…<=Begin[an]<End[an]可以證明，如果在可能的事件a1<a2<…<an中選取在時(shí)間上不重疊的最長(zhǎng)序列，那么一定存在一個(gè)包含a1（結(jié)束最早）的最長(zhǎng)序列。（證明：略）2023/1/913思考：請(qǐng)談?wù)勛约旱慕忸}思路2023/1/914練習(xí)題目：

2037今年暑假不AC2023/1/915

二、區(qū)間覆蓋問題

用i來表示x軸上坐標(biāo)為[i-1,i]的區(qū)間（長(zhǎng)度為1），并給出M(1=<M=<200)個(gè)不同的整數(shù)，表示M個(gè)這樣的區(qū)間?，F(xiàn)在讓你畫幾條線段覆蓋住所有的區(qū)間，條件是：每條線段可以任意長(zhǎng)，但是要求所畫線段之和最小，并且線段的數(shù)目不超過N(1=<N=<50)。例如：M=5個(gè)整數(shù)1、3、4、8和11表示區(qū)間，要求所用線段不超過N=3條012345678910112023/1/916算法分析：如果N>=M，那么顯然用M條長(zhǎng)度為1的線段可以覆蓋住所有的區(qū)間，所求的線段總長(zhǎng)為M。如果N=1，那么顯然所需線段總長(zhǎng)為：…如果N=2，相當(dāng)于N=1的情況下從某處斷開（從哪兒斷開呢？）。如果N=k呢？2023/1/917三、HDOJ_1050MovingTables題目鏈接SampleInput

3

4

1020

3040

5060

7080

2

13

2200

3

10100

2080

3050

SampleOutput

10

20

30

2023/1/918算法分析：1、如果沒有交叉，總時(shí)間應(yīng)該是多少？2、影響搬運(yùn)時(shí)間的因素是什么？3、如果每趟處理都包含最大重疊，處理后的效果是什么？4、得出什么結(jié)論？2023/1/919HDOJ_1050源碼：#include<iostream>usingnamespacestd;intmain(){intt,i,j,N,P[200];ints,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;}return0;}2023/1/920貪心算法的基本步驟

1、從問題的某個(gè)初始解出發(fā)。2、采用循環(huán)語句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局部最優(yōu)策略，得到一個(gè)部分解，縮小問題的范圍或規(guī)模。3、將所有部分解綜合起來，得到問題的最終解。2023/1/921貪心算法都很簡(jiǎn)單嗎？看一道難一些的。（2004年上海賽區(qū)試題：當(dāng)時(shí)算是簡(jiǎn)單題）2023/1/922ACM-ICPCAsiaRegional,

2004,ShanghaiProblemH

TianJi—TheHorseRacing2023/1/923示意圖：928371748795928371748795-200-200-200928371748795-200+200+2002023/1/924談?wù)勛约旱南敕ā?023/1/925Case1:King:200180160Tianji:1901701502023/1/926Case2:King:200180160Tianji:1801701502023/1/927Case3:King:200180160Tianji:1801551502023/1/928總體的思路是什么？2023/1/929提醒：

很多貪心類型的題目都象本題一樣，不是最樸素的貪心，而是需要做一些變化，對(duì)于我們，關(guān)鍵是找到貪心的本質(zhì)！2023/1/930本講重點(diǎn)：(連通網(wǎng)的)最小生成樹2023/1/931

假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？問題：2023/1/932

構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）該問題等價(jià)于：算法一：（普里姆算法）2023/1/933MST性質(zhì)：假設(shè)N={V,{E}}是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若（u,v）是一條具有最小權(quán)值的邊，其中u∈U,v∈V-U,則必定存在一棵包含邊（u,v）的最小生成樹。證明（略）。2023/1/934

取圖中任意一個(gè)頂點(diǎn)v作為生成樹的根，之后往生成樹上添加新的頂點(diǎn)w。在添加的頂點(diǎn)w和已經(jīng)在生成樹上的頂點(diǎn)v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有n-1個(gè)頂點(diǎn)為止。普里姆算法的基本思想:2023/1/935abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=672023/1/936

在生成樹的構(gòu)造過程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集U

和尚未落在生成樹上的頂點(diǎn)集V-U

，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。

一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:2023/1/937abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c552023/1/938具體做法:

先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止?？紤]問題的出發(fā)點(diǎn):

為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄?023/1/939abcdegf195141827168213ae12dcbgf7148531621例如:71218192023/1/940普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法2023/1/941請(qǐng)務(wù)必寫出自己的模版！2023/1/942再次提醒:

調(diào)課三周(11/6,11/13,11/20)2023/1/943附：貪心算法練習(xí)題：1045

FireNet105