C++算法(lecture_06)貪心算法

1、2022-3-221ACM ACM 程序設(shè)計(jì)程序設(shè)計(jì)2022-3-2222022-3-223你 了嗎？AC2022-3-224楓冰葉子楓冰葉子 2022-3-225貪心算法貪心算法（Greedy Algorithm）2022-3-226FatMouse Trade2022-3-227在對(duì)問(wèn)題求解時(shí)，總是作出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體上加以考慮，它所作出的僅僅是在某種意義上的局部最優(yōu)解（是否是全局最優(yōu)，需要證明）。2022-3-228若要用貪心算法求解某問(wèn)題的整若要用貪心算法求解某問(wèn)題的整體最優(yōu)解，必須首先證明貪心思體最優(yōu)解，必須首先證明貪心思想在該問(wèn)題的應(yīng)用結(jié)果就是最優(yōu)想在該問(wèn)

2、題的應(yīng)用結(jié)果就是最優(yōu)解！解！2022-3-2292022-3-22102022-3-2211 已知N個(gè)事件的發(fā)生時(shí)刻和結(jié)束時(shí)刻（見(jiàn)下表，表中事件已按結(jié)束時(shí)刻升序排序）。一些在時(shí)間上沒(méi)有重疊的事件，可以構(gòu)成一個(gè)事件序列，如事件2，8，10。事件序列包含的事件數(shù)目，稱(chēng)為該事件序列的長(zhǎng)度。請(qǐng)編程找出一個(gè)最長(zhǎng)的事件序列。事件編號(hào)01 2 3 4567891011發(fā)生時(shí)刻13 0 3 25641081515結(jié)束時(shí)刻34 7 8 9 10 12 14 15 18 19202022-3-2212l不妨用Begini和Endi表示事件i的開(kāi)始時(shí)刻和結(jié)束時(shí)刻。則原題的要求就是找一個(gè)最長(zhǎng)的序列a1a2an，滿(mǎn)足：

3、Begina1Enda1= BeginanEndan可以證明，如果在可能的事件可以證明，如果在可能的事件a1a2ana1a2an中選取在時(shí)間上不重疊的最長(zhǎng)序列，那么一定中選取在時(shí)間上不重疊的最長(zhǎng)序列，那么一定存在一個(gè)包含存在一個(gè)包含a1a1（結(jié)束最早）的最長(zhǎng)序列。（結(jié)束最早）的最長(zhǎng)序列。（證明：略）（證明：略）2022-3-2213l請(qǐng)談?wù)勛约旱慕忸}思路請(qǐng)談?wù)勛约旱慕忸}思路2022-3-22142022-3-2215用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)在讓你畫(huà)幾條線段覆蓋住所有的區(qū)間，條件是：每條線段可以任意長(zhǎng)，但是

4、要求所畫(huà)線段之和最小，并且線段的數(shù)目不超過(guò)N(1=N=M，那么顯然用M條長(zhǎng)度為1的線段可以覆蓋住所有的區(qū)間，所求的線段總長(zhǎng)為M。l如果N=1，那么顯然所需線段總長(zhǎng)為：l如果N=2，相當(dāng)于N=1的情況下從某處斷開(kāi)（從哪兒斷開(kāi)呢？）。l如果N=k呢？2022-3-2217l題目鏈接Sample Input3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50 Sample Output10 20 30 2022-3-22181、如果沒(méi)有交叉，總時(shí)間應(yīng)該是多少？2、影響搬運(yùn)時(shí)間的因素是什么？3、如果每趟處理都包含最大重疊，處理后 的效

5、果是什么？4、得出什么結(jié)論？2022-3-2219#include using namespace std; int main() int t,i,j,N,P200; int s,d,temp,k,min; cint; for(i=0;it;i+) for(j=0;jN; for(j=0;jsd; s=(s-1)/2; d=(d-1)/2; if(sd) temp=s; s=d; d=temp; for(k=s;k=d;k+) Pk+; min=-1; for(j=0;jmin) min=Pj; coutmin*10endl; return 0; 2022-3-22201、從問(wèn)題的某個(gè)初始解出

6、發(fā)。2、采用循環(huán)語(yǔ)句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局部最優(yōu)策略，得到一個(gè)部分解，縮小問(wèn)題的范圍或規(guī)模。3、將所有部分解綜合起來(lái)，得到問(wèn)題的最終解。2022-3-2221看一道難一些的。（2004年上海賽區(qū)試題：當(dāng)時(shí)算是簡(jiǎn)單題）2022-3-2222Problem H Tian JiThe Horse Racing2022-3-2223928371748795928371748795-200-200-200928371748795-200+200+2002022-3-22242022-3-2225King: 200 180 160Tianji: 190 170 1502022-3-2226

7、King: 200 180 160Tianji: 180 170 1502022-3-2227King: 200 180 160Tianji: 180 155 1502022-3-22282022-3-2229 很多貪心類(lèi)型的題目都象本題一樣，不是最樸素的貪心，而是需要做一些變化，對(duì)于我們，關(guān)鍵是找到貪心的本質(zhì)！2022-3-2230本講重點(diǎn)：本講重點(diǎn)：( (連通網(wǎng)的連通網(wǎng)的) )最小生成樹(shù)最小生成樹(shù)2022-3-2231 假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n-1條線路，如何在最節(jié)省經(jīng)如何在最節(jié)省經(jīng)費(fèi)的前提下建立費(fèi)的前提下建立這個(gè)通訊網(wǎng)通訊網(wǎng)？問(wèn)題：?jiǎn)栴}：2

8、022-3-2232 構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即： 在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成回路），使“權(quán)值之和權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）算法二：（克魯斯卡爾算法）該問(wèn)題等價(jià)于：該問(wèn)題等價(jià)于：算法一：（普里姆算法）算法一：（普里姆算法）2022-3-2233l假設(shè)假設(shè)N=V,EN=V,E是一個(gè)連通網(wǎng)，是一個(gè)連通網(wǎng)， U U是頂是頂點(diǎn)集點(diǎn)集 V V的一個(gè)非空子集。若（的一個(gè)非空子集。若（u,vu,v）是）是一條具有最小權(quán)值的邊，其中一條具有最小權(quán)值的邊，其中uU, uU, vV-U,vV-U,則必定存在一棵包含邊（則必定存在一棵包含邊（u,vu,v）的最小生成樹(shù)。的最小生

9、成樹(shù)。l證明（略）。證明（略）。2022-3-2234 取圖中任意一個(gè)頂點(diǎn) v 作為生成樹(shù)的根，之后往生成樹(shù)上添加新的頂點(diǎn) w。在添加的在添加的頂點(diǎn)頂點(diǎn) w 和已經(jīng)在生成樹(shù)上的頂點(diǎn)和已經(jīng)在生成樹(shù)上的頂點(diǎn)v 之間必之間必定存在一條邊，并且該邊的權(quán)值在所有連定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)通頂點(diǎn) v 和和 w 之間的邊中取值最小之間的邊中取值最小。之后繼續(xù)往生成樹(shù)上添加頂點(diǎn)，直至生成樹(shù)上含有 n-1 個(gè)頂點(diǎn)為止。普里姆算法的基本思想普里姆算法的基本思想:2022-3-2235abcdegf例如例如: :195141827168213ae12dcbgf7148531621所得生成樹(shù)權(quán)值和=

10、 14+8+3+5+16+21 = 672022-3-2236 在生成樹(shù)的構(gòu)造過(guò)程中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集 U 和尚未落在生成樹(shù)上的頂點(diǎn)集V-U ，則應(yīng)在所有連通在所有連通U中頂點(diǎn)和中頂點(diǎn)和V-U中中頂點(diǎn)的邊中選取權(quán)值最小的邊頂點(diǎn)的邊中選取權(quán)值最小的邊。 一般情況下所添加的頂點(diǎn)應(yīng)滿(mǎn)足下列條件:2022-3-2237abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c5 52022-3-2238具體做法具體做法: 先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不

11、使SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止?？紤]問(wèn)題的出發(fā)點(diǎn)考慮問(wèn)題的出發(fā)點(diǎn): 為使生成樹(shù)上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄嚎唆斔箍査惴ǖ幕舅枷耄?022-3-2239abcdegf195141827168213ae12dcbgf7148531621例如例如: :71218192022-3-2240普里姆算法普里姆算法 克魯斯卡爾算法克魯斯卡爾算法時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稠密圖稀疏圖稀疏圖算法名算法名適應(yīng)范圍適應(yīng)范圍比較兩種算法比較兩種算法2022-3-22412022-3-22422022-3-2243l1045 Fire Netl1050 Moving Tablesl1051 Wooden Sticks