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