貪心算法教學(xué)提綱

貪心(tānxīn)算法

by

hyliu第一頁，共13頁。貪心法是什么？ 貪心法就是遵循某種規(guī)律，不斷貪心地選取當(dāng)前最優(yōu)策略的算法(suànfǎ)設(shè)計(jì)方法。第二頁，共13頁。硬幣(yìngbì)問題題目大意:有1元、5元、10元、50元、100元、500元的硬幣各C1、C5、C10、C50、C100、C500枚?，F(xiàn)在要用這些硬幣來支付A元，最少需要(xūyào)多少枚硬幣？假定本題至少存在一種支付方案。限制條件0<=C1,C5,C10,C50,C100,C500<=10^90<=A<=10^9第三頁，共13頁。區(qū)間調(diào)度(diàodù)問題題目大意:有n項(xiàng)工作，每項(xiàng)工作分別在S[i]時(shí)間開始，在T[i]時(shí)間結(jié)束。對(duì)于每項(xiàng)工作，你都有可以選擇參與(cānyù)與否。如果選擇了參與(cānyù)，那么自始自終都必須全程參與(cānyù)。

此外，參與(cānyù)工作的時(shí)間段不能重疊（即使是開始的瞬間和結(jié)束的瞬間的重疊也是不允許的），目標(biāo)是盡可能參加更多的工作,問最多能參加多少項(xiàng)工作。限制條件: 1<=N<=100000 1<=si<=ti<=10^9第四頁，共13頁。貪心(tānxīn)策略 (1)在可選的工作中，每次選取結(jié)束時(shí)間最早的工作。 (2)在可選的工作中，每次選取用時(shí)最短的工作。 (3)在可選的工作中，每次都選取與最少可選工作有重復(fù)的工作。第五頁，共13頁。POJ

3617題目大意： 給定長度為N的字符串S，要構(gòu)造一個(gè)長度為N的字符串T。起初(qǐchū)，T是一個(gè)空串，隨后反復(fù)進(jìn)行下列任意操作。從S的頭部刪除一個(gè)字符，加到T的尾部從S的尾部刪除一個(gè)字符，加到T的尾部 目標(biāo)是構(gòu)造字典序盡可能小的字符串。限制條件： 1<=N<=2000 字符串S只包含大寫英文字母。第六頁，共13頁。貪心策略 idea1： 不斷取S的開頭和末尾(mòwěi)中較小的一個(gè)字符放到T的末尾(mòwěi) idea2: 按照字典序比較S與S’,S’為S的反轉(zhuǎn)。 S字典序較小則取頭，反之則取尾。

第七頁，共13頁。POJ

3069題目大意: 一個(gè)直線上有N個(gè)點(diǎn)。點(diǎn)i的位置是Xi。從這些點(diǎn)中選取若干個(gè)加上標(biāo)記。要求：對(duì)于(duìyú)每個(gè)點(diǎn)，與其距離為R的范圍內(nèi)必有做標(biāo)記的點(diǎn)（包括自身）。求至少標(biāo)記多少點(diǎn)才能滿足要求。 輸入：N，R，以及N個(gè)點(diǎn)各自距原點(diǎn)的距離（①不一定按照順序，故需要排序②可以重疊）。

輸出：被標(biāo)記的點(diǎn)的最少個(gè)數(shù)。限制條件: 1<=N<=1000 0<=R<=1000 0<=Xi<=1000第八頁，共13頁。貪心(tānxīn)策略: 每次尋找未被覆蓋的點(diǎn)，向右找在R范圍內(nèi)距離其最遠(yuǎn)的點(diǎn)作為標(biāo)記點(diǎn)。第九頁，共13頁。POJ

3253題目大意: 有一個(gè)農(nóng)夫要把一個(gè)木板鉅成幾塊給定長度的小木板，每次鋸都要收取一定(yīdìng)費(fèi)用，這個(gè)費(fèi)用就是當(dāng)前鋸的這個(gè)木版的長度給定各個(gè)要求的小木板的長度，及小木板的個(gè)數(shù)n，求最小費(fèi)用限制條件: 1<=N<=20000 0<=Li<=50000第十頁，共13頁。POJ

3253題目大意: 有一個(gè)農(nóng)夫要把一個(gè)木板鉅成幾塊給定(ɡěidìnɡ)長度的小木板，每次鋸都要收取一定費(fèi)用，這個(gè)費(fèi)用就是當(dāng)前鋸的這個(gè)木版的長度給定(ɡěidìnɡ)各個(gè)要求的小木板的長度，及小木板的個(gè)數(shù)n，求最小費(fèi)用限制條件: 1<=N<=20000 0<=Li<=50000第十一頁，共13頁。POJ

3253題目(tímù)大意: 有一個(gè)農(nóng)夫要把一個(gè)木板鉅成幾塊給定長度的小木板，每次鋸都要收取一定費(fèi)用，這個(gè)費(fèi)用就是當(dāng)前鋸的這個(gè)木版的長度給定各個(gè)要求的小木板的