【背景知識】
【貪心算法】顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體 最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法 得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解， 但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一 些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。
【貪心算法的基本要素】
對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有兩個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。
【貪心選擇性質(zhì)】
所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個基本要素。貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式做出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。
【最優(yōu)子結(jié)構(gòu)性質(zhì)】
當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(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 }這是個最基本的貪心算法模型，但是包含了基本的思路模式：首先分析系統(tǒng)的特性，找到基本的最小模型。此題中老鼠要用有限的貓糧換取自己的食物，不同的倉庫不一樣，先根據(jù)性價比進(jìn)行排序。（ 貪心算法都有排序，不同的模型的排序?qū)ο蟛煌? ） 然后從性價比最高到最低開始遍歷，如果手上的貓糧夠，就換取性價比最高的食物，如果不夠，就換取相應(yīng)的比例，一直到貓糧耗盡。最后得到的就是能獲得的最多貓糧。
模型二：暑假不AC ?
Problem Description
“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”
確實如此，世界杯來了，球迷的節(jié)日也來了，估計很多ACMer也會拋開電腦，奔向電視了。
作為球迷，一定想看盡量多的完整的比賽，當(dāng)然，作為新時代的好青年，你一定還會看一些其它的節(jié)目，比如新聞聯(lián)播（永遠(yuǎn)不要忘記關(guān)心國家大事）、非常6+7、超級女生，以及王小丫的《開心辭典》等等，假設(shè)你已經(jīng)知道了所有你喜歡看的電視節(jié)目的轉(zhuǎn)播時間表，你會合理安排嗎？（目標(biāo)是能看盡量多的完整節(jié)目）?
Input輸入數(shù)據(jù)包含多個測試實例，每個測試實例的第一行只有一個整數(shù)n(n<=100)，表示你喜歡看的節(jié)目的總數(shù)，然后是n行數(shù)據(jù)，每行包括兩個數(shù)據(jù)Ti_s,Ti_e (1<=i<=n)，分別表示第i個節(jié)目的開始和結(jié)束時間，為了簡化問題，每個時間都用一個正整數(shù)表示。n=0表示輸入結(jié)束，不做處理。Output對于每個測試實例，輸出能完整看到的電視節(jié)目的個數(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 也是問題的最優(yōu)解，在余下的問題里，繼續(xù)拿最早結(jié)束的；
2、拿可以開始的最早結(jié)束。(所以要按結(jié)束時間排序一次，然后把可以開始的選擇上，然后繼續(xù)向后推)
把輸入的數(shù)據(jù)按照 電視節(jié)目結(jié)束的時間從小到大進(jìn)行排序 （排序的目的是使取的結(jié)束時間都比剩下的結(jié)束時間要早 這樣才能看更多的節(jié)目） 對應(yīng)的開始時間也進(jìn)行了排序???
然后從第一個結(jié)束時間開始 尋找下一個比他晚的開始時間 如果找到了 節(jié)目數(shù)就加1（初始的節(jié)目數(shù)為1 因為選了第一個結(jié)束時間就是一個節(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); // 對數(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)，記錄要對比的最早時刻 } } printf( " %d\n " ,count); } return 0 ; }模型三：零件加工問題：
【問題描述】有個國有中型企業(yè)，接到一批需要加工零件的訂單，員工們非常高興，可是高興之后卻發(fā)現(xiàn)問題了，原來這家企業(yè)能夠加工這批零件的機(jī)床有限，如?果僅僅為了這批加工任務(wù)而新添機(jī)床的話，那么既不合算也不必要，因為加工完這批零件后很可能這些機(jī)床又要閑置起來，所以大批量購買肯定不行，但這批訂單又必須要完成，那么這么辦呢？很想請你幫忙設(shè)計一個安排加工任務(wù)，使得完成這批訂單所需要使用的機(jī)器數(shù)量最少。假定對于待加工的第個零件，給你兩個非負(fù)整數(shù)，，其中表示加工開始的時間，其中表示加工結(jié)束的時間，由于受到客觀條件的制約，開始和結(jié)束的時間限制必須要遵守。當(dāng)然在某個時刻一臺機(jī)器只能加工一個零件。
【輸入說明】本問題有多組測試數(shù)據(jù)，對于每組測試數(shù)據(jù)，輸入的第一行是需要加工的零件個數(shù)，接著是行，其中，如上所述。
【輸出說明】輸出只有一行，就是完成加工任務(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ù)備（排序）：按照零件加工的起始時間和結(jié)束時間進(jìn)行排序，注意排序的主關(guān)鍵字是起始時間，當(dāng)起始時間相同時才要按照結(jié)束結(jié)束時間排序。
b)?? 第一步：如果沒有零件需要加工，那么當(dāng)然需要的機(jī)床數(shù)是零。
c)?? 第二步：如果有零件需要加工，那么至少需要一臺機(jī)床。
d)?? 第三步：如果在現(xiàn)有的機(jī)床上能夠加工新的零件，那么就不需要增加新的機(jī)床，如果安排不下，才要增加一臺機(jī)床。
e)?? 第四步：重復(fù)第三步，直到所有的零件都有機(jī)床來加工。
【算法優(yōu)化】
算法的第一步、第二步和第四步是沒什么可優(yōu)化的，下面我們來分析一下算法的第三步。
如果能安排的下，就是指“零件和機(jī)床不矛盾”，現(xiàn)在機(jī)床可不是一臺，有很多臺，所以只要找到一臺機(jī)床能安排下就可以了，如果所有的機(jī)床都找遍了，還是安排不下，那么只有增加機(jī)床。設(shè)當(dāng)前已經(jīng)有臺機(jī)床，分別是，新的待加工的零件是第個零件，這樣我們可以描述“查找可以在臺機(jī)床里的哪臺能安排的算法”了。
#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);這里兩行只差一個空格，有差別的空格是有意義的！ } } 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ù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
