貪心算法

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

貪心算法byhyliu第一頁，共十四頁。

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

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

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

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

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

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

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

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

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

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

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

12謝謝第十三頁，共十四頁。

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