貪心算法教學提綱

貪心(tānxīn)算法

by

hyliu第一頁，共13頁。貪心法是什么？ 貪心法就是遵循某種規(guī)律，不斷貪心地選取當前最優(yōu)策略的算法(suànfǎ)設計方法。第二頁，共13頁。硬幣(yìngbì)問題題目大意:有1元、5元、10元、50元、100元、500元的硬幣各C1、C5、C10、C50、C100、C500枚。現(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項工作，每項工作分別在S[i]時間開始，在T[i]時間結(jié)束。對于每項工作，你都有可以選擇參與(cānyù)與否。如果選擇了參與(cānyù)，那么自始自終都必須全程參與(cānyù)。

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

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

第七頁，共13頁。POJ

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

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

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

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

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