【背景知識(shí)】
【貪心算法】顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體 最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法 得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解， 但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹問(wèn)題等。在一 些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。
【貪心算法的基本要素】
對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類問(wèn)題一般具有兩個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。
【貪心選擇性質(zhì)】
所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素。貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式做出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。
【最優(yōu)子結(jié)構(gòu)性質(zhì)】
當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法求解的關(guān)鍵特征。
模型一：最基本的模型
- 題目描述：
-
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.?
- 輸入：
-
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
- 輸出：
-
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
- 樣例輸入：
-
5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1
- 樣例輸出：
-
13.333 31.5001 #include<stdio.h> 2 #include<algorithm> 3 using namespace std; 4 struct Trade 5 { 6 int j,f; 7 double percent; 8 }mouse[ 3001 ]; 9 bool cmp(Trade a,Trade b) 10 { 11 return a.percent> b.percent; 12 } 13 int main() 14 { 15 int n,m; 16 while (scanf( " %d%d " ,&m,&n)!=EOF&&(n!=- 1 ||m!=- 1 )) 17 { 18 int i; 19 20 for (i= 0 ;i<n;i++ ) 21 { 22 scanf( " %d%d " ,&mouse[i].j,& mouse[i].f); 23 mouse[i].percent=( double )mouse[i].j/ mouse[i].f; 24 } 25 sort(mouse,mouse+ n,cmp); 26 double sum= 0 ; 27 for (i= 0 ;i<n;i++ ) 28 { 29 if (m> mouse[i].f) 30 { 31 sum+= mouse[i].j; 32 m-= mouse[i].f; 33 } 34 else 35 // break; 36 { 37 sum+=mouse[i].percent* m; 38 m= 0 ; 39 break ; 40 } 41 42 43 } 44 45 printf( " %.3lf\n " ,sum); 46 47 } 48 return 0 ; 49 }這是個(gè)最基本的貪心算法模型，但是包含了基本的思路模式：首先分析系統(tǒng)的特性，找到基本的最小模型。此題中老鼠要用有限的貓糧換取自己的食物，不同的倉(cāng)庫(kù)不一樣，先根據(jù)性價(jià)比進(jìn)行排序。（ 貪心算法都有排序，不同的模型的排序?qū)ο蟛煌? ） 然后從性價(jià)比最高到最低開始遍歷，如果手上的貓糧夠，就換取性價(jià)比最高的食物，如果不夠，就換取相應(yīng)的比例，一直到貓糧耗盡。最后得到的就是能獲得的最多貓糧。
模型二：暑假不AC ?
Problem Description
“今年暑假不AC？”
“是的?！?
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”
確實(shí)如此，世界杯來(lái)了，球迷的節(jié)日也來(lái)了，估計(jì)很多ACMer也會(huì)拋開電腦，奔向電視了。
作為球迷，一定想看盡量多的完整的比賽，當(dāng)然，作為新時(shí)代的好青年，你一定還會(huì)看一些其它的節(jié)目，比如新聞聯(lián)播（永遠(yuǎn)不要忘記關(guān)心國(guó)家大事）、非常6+7、超級(jí)女生，以及王小丫的《開心辭典》等等，假設(shè)你已經(jīng)知道了所有你喜歡看的電視節(jié)目的轉(zhuǎn)播時(shí)間表，你會(huì)合理安排嗎？（目標(biāo)是能看盡量多的完整節(jié)目）?
Input輸入數(shù)據(jù)包含多個(gè)測(cè)試實(shí)例，每個(gè)測(cè)試實(shí)例的第一行只有一個(gè)整數(shù)n(n<=100)，表示你喜歡看的節(jié)目的總數(shù)，然后是n行數(shù)據(jù)，每行包括兩個(gè)數(shù)據(jù)Ti_s,Ti_e (1<=i<=n)，分別表示第i個(gè)節(jié)目的開始和結(jié)束時(shí)間，為了簡(jiǎn)化問(wèn)題，每個(gè)時(shí)間都用一個(gè)正整數(shù)表示。n=0表示輸入結(jié)束，不做處理。Output對(duì)于每個(gè)測(cè)試實(shí)例，輸出能完整看到的電視節(jié)目的個(gè)數(shù)，每個(gè)測(cè)試實(shí)例的輸出占一行。?
Sample Input12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0? ?Sample Output51、若A是E的最優(yōu)解，那么E-A 也是問(wèn)題的最優(yōu)解，在余下的問(wèn)題里，繼續(xù)拿最早結(jié)束的；
2、拿可以開始的最早結(jié)束。(所以要按結(jié)束時(shí)間排序一次，然后把可以開始的選擇上，然后繼續(xù)向后推)
把輸入的數(shù)據(jù)按照 電視節(jié)目結(jié)束的時(shí)間從小到大進(jìn)行排序 （排序的目的是使取的結(jié)束時(shí)間都比剩下的結(jié)束時(shí)間要早 這樣才能看更多的節(jié)目） 對(duì)應(yīng)的開始時(shí)間也進(jìn)行了排序???
然后從第一個(gè)結(jié)束時(shí)間開始 尋找下一個(gè)比他晚的開始時(shí)間 如果找到了 節(jié)目數(shù)就加1（初始的節(jié)目數(shù)為1 因?yàn)檫x了第一個(gè)結(jié)束時(shí)間就是一個(gè)節(jié)目了）#include<stdio.h> #include <iostream> #include <vector> #include <algorithm> using namespace std; struct SE { int Ti_s; int Ti_e; }; bool cmp(SE a, SE b) { if (a.Ti_e < b.Ti_e) return true ; else return false ; } int main() { int n; while (scanf( " %d " ,&n)!=EOF && n!= 0 ) { vector <SE> v; for ( int i= 0 ;i<n;i++ ) { SE se; scanf( " %d %d " ,&se.Ti_s,& se.Ti_e); v.push_back(se); } sort(v.begin(),v.end(),cmp); // 對(duì)數(shù)據(jù)以Ti_e進(jìn)行升序排序 int flag= 0 ,count= 1 ; for ( int j= 1 ;j<n;j++ ) { if (v[j].Ti_s>= v[flag].Ti_e) { count ++ ; flag =j; // 不斷向前推進(jìn)，記錄要對(duì)比的最早時(shí)刻 } } printf( " %d\n " ,count); } return 0 ; }模型三：零件加工問(wèn)題：
【問(wèn)題描述】有個(gè)國(guó)有中型企業(yè)，接到一批需要加工零件的訂單，員工們非常高興，可是高興之后卻發(fā)現(xiàn)問(wèn)題了，原來(lái)這家企業(yè)能夠加工這批零件的機(jī)床有限，如?果僅僅為了這批加工任務(wù)而新添機(jī)床的話，那么既不合算也不必要，因?yàn)榧庸ね赀@批零件后很可能這些機(jī)床又要閑置起來(lái)，所以大批量購(gòu)買肯定不行，但這批訂單又必須要完成，那么這么辦呢？很想請(qǐng)你幫忙設(shè)計(jì)一個(gè)安排加工任務(wù)，使得完成這批訂單所需要使用的機(jī)器數(shù)量最少。假定對(duì)于待加工的第個(gè)零件，給你兩個(gè)非負(fù)整數(shù)，，其中表示加工開始的時(shí)間，其中表示加工結(jié)束的時(shí)間，由于受到客觀條件的制約，開始和結(jié)束的時(shí)間限制必須要遵守。當(dāng)然在某個(gè)時(shí)刻一臺(tái)機(jī)器只能加工一個(gè)零件。
【輸入說(shuō)明】本問(wèn)題有多組測(cè)試數(shù)據(jù)，對(duì)于每組測(cè)試數(shù)據(jù)，輸入的第一行是需要加工的零件個(gè)數(shù)，接著是行，其中，如上所述。
【輸出說(shuō)明】輸出只有一行，就是完成加工任務(wù)所需要的最少機(jī)床數(shù)。
【Sample?Input】
7
[6，9]
[1，4]
[2，5]
[3，7]
[4，7]
[1，3]
[7，8]
【Sample?Output】
3
a)?? 預(yù)備（排序）：按照零件加工的起始時(shí)間和結(jié)束時(shí)間進(jìn)行排序，注意排序的主關(guān)鍵字是起始時(shí)間，當(dāng)起始時(shí)間相同時(shí)才要按照結(jié)束結(jié)束時(shí)間排序。
b)?? 第一步：如果沒(méi)有零件需要加工，那么當(dāng)然需要的機(jī)床數(shù)是零。
c)?? 第二步：如果有零件需要加工，那么至少需要一臺(tái)機(jī)床。
d)?? 第三步：如果在現(xiàn)有的機(jī)床上能夠加工新的零件，那么就不需要增加新的機(jī)床，如果安排不下，才要增加一臺(tái)機(jī)床。
e)?? 第四步：重復(fù)第三步，直到所有的零件都有機(jī)床來(lái)加工。
【算法優(yōu)化】
算法的第一步、第二步和第四步是沒(méi)什么可優(yōu)化的，下面我們來(lái)分析一下算法的第三步。
如果能安排的下，就是指“零件和機(jī)床不矛盾”，現(xiàn)在機(jī)床可不是一臺(tái)，有很多臺(tái)，所以只要找到一臺(tái)機(jī)床能安排下就可以了，如果所有的機(jī)床都找遍了，還是安排不下，那么只有增加機(jī)床。設(shè)當(dāng)前已經(jīng)有臺(tái)機(jī)床，分別是，新的待加工的零件是第個(gè)零件，這樣我們可以描述“查找可以在臺(tái)機(jī)床里的哪臺(tái)能安排的算法”了。
#include<iostream> #include <algorithm> using namespace std; #define MAX 1001 structstuTime { intnSi; intnEi; }; stuTimestuPart[MAX],stuMachine[MAX]; void vInit(); void vInput(intnP); boolbCmp(conststuTime &stuA,conststuTime& stuB); void vSort(intnP); intnGetMachine(intnP); void vOut(intnM); intnFind(intnP,intnM); int main() { intnPart; intnMachine; while ( 1 ==scanf( " %d " ,& nPart)) { vInit(); vInput(nPart); vSort(nPart); nMachine = nGetMachine(nPart); vOut(nMachine); } return 0 ; } void vInit() { memset(stuPart, 0 , sizeof (stuPart)); memset(stuMachine, 0 , sizeof (stuMachine)); } void vInput(intnP) { int i; for (i= 1 ;i<=nP;i++ ) { scanf( " [%d,%d] " ,&stuPart[i].nSi,& stuPart[i].nEi); // scanf("[%d,%d]",&stuPart[i].nSi,&stuPart[i].nEi);這里兩行只差一個(gè)空格，有差別的空格是有意義的！ } } boolbCmp(conststuTime &stuA,conststuTime& stuB) { if (stuA.nSi== stuB.nSi) return (stuA.nEi< stuB.nEi); return (stuA.nSi< stuB.nSi); } void vSort(intnP) { sort( &stuPart[ 1 ],&stuPart[nP+ 1 ],bCmp); } intnGetMachine(intnP) { intnRet; int i; intnTemp; nRet = 0 ; for (i= 1 ;i<=nP;i++ ) { nTemp = nFind(i,nRet); if (nTemp<= nRet) { stuMachine[nTemp].nEi = stuPart[i].nEi; } else { nRet ++ ; stuMachine[nRet].nSi = stuPart[i].nSi; stuMachine[nRet].nEi = stuPart[i].nEi; } } return nRet; } void vOut(intnM) { printf( " %d\n " ,nM); } intnFind(intnP,intnM) { int i; for (i= 1 ;i<=nM;i++ ) { if (stuPart[nP].nSi>= stuMachine[i].nEi) { return i; } } return i; }注意此模型與前邊的聯(lián)系與區(qū)別，總結(jié)一般的規(guī)律，應(yīng)用到實(shí)際的算法中。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
