貪心算法

《貪心算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

貪心算法byhyliu第一頁(yè)，共十四頁(yè)。

1貪心法是什么？貪心法就是遵循某種規(guī)律，不斷貪心地選取當(dāng)前最優(yōu)策略的算法設(shè)計(jì)方法。第二頁(yè)，共十四頁(yè)。

2硬幣問(wèn)題題目大意:有1元、5元、10元、50元、100元、500元的硬幣各C1、C5、C10、C50、C100、C500枚?，F(xiàn)在要用這些硬幣來(lái)支付A元，最少需要多少枚硬幣？假定本題至少存在一種支付方案。限制條件0<=C1,C5,C10,C50,C100,C500<=10^90<=A<=10^9第三頁(yè)，共十四頁(yè)。

3區(qū)間調(diào)度問(wèn)題題目大意:有n項(xiàng)工作，每項(xiàng)工作分別在S[i]時(shí)間開(kāi)始，在T[i]時(shí)間結(jié)束。對(duì)于每項(xiàng)工作，你都有可以選擇參與與否。如果選擇了參與，那么自始自終都必須全程參與。?此外，參與工作的時(shí)間段不能重疊（即使是開(kāi)始的瞬間和結(jié)束的瞬間的重疊也是不允許的），目標(biāo)是盡可能參加更多的工作,問(wèn)最多能參加多少項(xiàng)工作。限制條件:1<=N<=1000001<=si<=ti<=10^9第四頁(yè)，共十四頁(yè)。

4貪心策略(1)在可選的工作中，每次選取結(jié)束時(shí)間最早的工作。(2)在可選的工作中，每次選取用時(shí)最短的工作。(3)在可選的工作中，每次都選取與最少可選工作有重復(fù)的工作。第五頁(yè)，共十四頁(yè)。

5POJ3617題目大意：給定長(zhǎng)度為N的字符串S，要構(gòu)造一個(gè)長(zhǎng)度為N的字符串T。起初，T是一個(gè)空串，隨后反復(fù)進(jìn)行下列任意操作。從S的頭部刪除一個(gè)字符，加到T的尾部從S的尾部刪除一個(gè)字符，加到T的尾部目標(biāo)是構(gòu)造字典序盡可能小的字符串。限制條件：1<=N<=2000字符串S只包含大寫(xiě)英文字母。第六頁(yè)，共十四頁(yè)。

6貪心策略idea1：不斷取S的開(kāi)頭和末尾中較小的一個(gè)字符放到T的末尾idea2:按照字典序比較S與S’,S’為S的反轉(zhuǎn)。S字典序較小則取頭，反之則取尾。第七頁(yè)，共十四頁(yè)。

7POJ3069題目大意:一個(gè)直線上有N個(gè)點(diǎn)。點(diǎn)i的位置是Xi。從這些點(diǎn)中選取若干個(gè)加上標(biāo)記。要求：對(duì)于每個(gè)點(diǎn)，與其距離為R的范圍內(nèi)必有做標(biāo)記的點(diǎn)（包括自身）。求至少標(biāo)記多少點(diǎn)才能滿(mǎn)足要求。輸入：N，R，以及N個(gè)點(diǎn)各自距原點(diǎn)的距離（①不一定按照順序，故需要排序②可以重疊）。輸出：被標(biāo)記的點(diǎn)的最少個(gè)數(shù)。限制條件:1<=N<=10000<=R<=10000<=Xi<=1000第八頁(yè)，共十四頁(yè)。

8貪心策略:每次尋找未被覆蓋的點(diǎn)，向右找在R范圍內(nèi)距離其最遠(yuǎn)的點(diǎn)作為標(biāo)記點(diǎn)。第九頁(yè)，共十四頁(yè)。

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

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

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

12謝謝第十三頁(yè)，共十四頁(yè)。

13內(nèi)容總結(jié)貪心算法。貪心法就是遵循某種規(guī)律，不斷貪心地選取當(dāng)前最優(yōu)策略的算法設(shè)計(jì)方法。題目大意:有1元、5元、10元、50元、100元、500元的硬幣各C1、C5、C10、C50、C100、C500枚?，F(xiàn)在要用這些硬幣來(lái)支付A元，最少需要多少枚硬幣。0<=C1,C5,C10,C50,C100,C500<=10^9。0<=A<=10^9。如果選擇了參與，那么自始自終都必須全程參與。按照字典序比較S與S’,S’為S的反轉(zhuǎn)第十四頁(yè)，共十四頁(yè)。