技術(shù)類貪心算法

ACM程序設(shè)計(jì)杭州電子科技大學(xué)劉春英acm@2023/1/102這學(xué)期，你了嗎？練習(xí)2023/1/103每周一星（8）：qzx

2023/1/104第九講貪心算法

（GreedyAlgorithm）2023/1/105導(dǎo)引問題：FatMouse'Trade2023/1/106所謂“貪心算法”是指：

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

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

已知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/1010算法分析：不妨用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/1011思考：請(qǐng)談?wù)勛约旱慕忸}思路2023/1/1012思考題2037今年暑假不AC2023/1/1013

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

用i來(lá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/1014算法分析：如果N>=M，那么顯然用M條長(zhǎng)度為1的線段可以覆蓋住所有的區(qū)間，所求的線段總長(zhǎng)為M。如果N=1，那么顯然所需線段總長(zhǎng)為：…如果N=2，相當(dāng)于N=1的情況下從某處斷開（從哪兒斷開呢？）。如果N=k呢？2023/1/1015三、HDOJ_1050MovingTablesSampleInput

3

4

1020

3040

5060

7080

2

13

2200

3

10100

2080

3050

SampleOutput

10

20

30

2023/1/1016算法分析：1、如果沒有交叉，總時(shí)間應(yīng)該是多少？2、影響搬運(yùn)時(shí)間的因素是什么？3、如果每趟處理都包含最大重疊，處理后的效果是什么？4、得出什么結(jié)論？2023/1/1017附:參考源碼(HDOJ-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/1018貪心算法的基本步驟

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

2004,ShanghaiTianJi—TheHorseRacing2023/1/1021示意圖：928371748795928371748795-200-200-200928371748795-200+200+2002023/1/1022談?wù)勛约旱南敕ò伞?023/1/1023Case1:King:200180160Tianji:1901701502023/1/1024Case2:King:200180160Tianji:1801701502023/1/1025Case3:King:200180160Tianji:1801551502023/1/1026總體的思路是什么？2023/1/1027提醒：

很多貪心類型的題目都象本題一樣，不是最樸素的貪心，而是需要做一些變化，對(duì)于我們，關(guān)鍵是找到貪心的本質(zhì)！2023/1/1028最后一個(gè)思考題Anyqu