《算法筆記》總結No.6—

一.簡單貪心

????????貪心法是求解一類最優化問題的方法，它總是考慮在當前狀態下局部最優(或較優)之后，來使全局的結果達到最優(或較優)的策略。顯然，如果采取較優而非最優的策略(最優策略可能不存在或是不易想到)，得到的全局結果也無法是最優的。而要獲得最優結果，則要求中間的每步策略都是最優的，因此嚴謹使用貪心法來求解最優化問題需要對采取的策略進行證明。證明的一般思路是使用反證法及數學歸納法，即假設策略不能導致最優解，然后通過一系列推導來得到矛盾，以此證明策略是最優的，最后用數學歸納法保證全局最優。不過對平常使用來說，也許沒有時間或不太容易對想到的策略進行嚴謹的證明(貪心的證明往往比貪本身更難)，因此一般來說，如果在想到某個似乎可行的策略之后，并且自己無法舉出反例，那么就勇敢地實現它。

1.組個最小數

給定數字0~9各若干個，可以任意順序排列這些數字，但必須全部使用，且使目標數字盡可能小（當然0不能做首位）比如輸入兩個0、兩個1、三個5和一個8，得到的最小數字就是100155858。

相信大家一下子就可以看出來策略：先從1~9中選擇不為0的最小數輸出，然后從0~9輸出數字，每個數字輸出次數為其剩余個數。

策略正確的證明：

首先由于所有數字都必須參與組合，因此最后結果的位數是確定的。?
由于最高位不為0，則選一個盡可能小的數作為首位——最高位定理
其余位數也應該從小到大輸出~

教材上的實在是太抽象了，好像有點錯誤，這里博主自己寫了一種：

#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;int main() {	vector<int> V;for(int i=1;i<=10;i++){int temp=0;cin>>temp;V.push_back(temp);}sort(V.begin(),V.end());  //直接排成升序 int flag=0;  //標記 for(int i=0;i<=9;i++)if(V[i]!=0){int temp=V[i];V[i]=V[0];V[0]=temp;flag=i;//保存第一個不為0的位置 break;	}for(int i=flag+1;i<=9;i++)  //找更小的頭，直接從flag下一位開始即可，節省時間~ if(V[i]<V[0]&&V[i]!=0){int temp=V[i];V[i]=V[0];V[0]=temp;}for(int i=0;i<=9;i++)cout<<V[i];
}

邏輯上沒什么難度，主要是要想清楚~

2.月餅庫存

輸入：第一行輸入N和M：N位月餅的種類數目，M位市場對月餅的需求總量；接下來的兩行均要輸入N個數：第一行的N個數分別對應當前種類的月餅全部賣出后可以掙多少，而第二行的N個數對應當前月餅的總數量~
要求輸出：在規定需求量下最高收入

????????試想一下你如果作為老板，會怎么去“貪得無厭”？很明顯——只需要在有限的需求量中，盡可能多的賣出單價最貴的月餅，豈不是可以收貨最多的營業額？如下博主自己寫的一種實現，和教材上的也不太一樣：

#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;struct mooncake{double num;  //總數 double income;  //總收入 double price;   //單價，需要自己計算 
}; int main() {int N,M;cin>>N>>M;vector<mooncake> V;for(int i=1;i<=N;i++) {mooncake temp;V.push_back(temp);}cout<<"請輸入數量："<<endl;for(int i=1;i<=N;i++) {double num=0;cin>>num;V[i-1].num=num;}cout<<"請輸入總價："<<endl;for(int i=1;i<=N;i++) {double income=0;cin>>income;V[i-1].income=income;}for(int i=0;i<=N-1;i++) V[i].price=V[i].income/V[i].num; //計算單價//按單價降序排列！保證貴的盡可能多賣for(int i=0;i<=V.size()-1;i++){for(int j=i;j<=V.size()-1;j++)    if(V[j].price>V[i].price)    {mooncake temp;temp=V[j];V[j]=V[i];V[i]=temp;}}for(int i=0;i<=V.size()-1;i++)cout<<"單價第"<<(i+1)<<"高的值為："<<V[i].income<<" "<<V[i].price<<" "<<V[i].num<<endl;for(int i=0;i<=N-1;i++)cout<<V[i].num<<endl; int j=0;  //使用的下標 double count=0;  //總利潤 while(M>0)  //當還有需求量時 {double doubt=0;doubt=M-V[j].num; //用M減去當前類型的額總量 if(doubt>=0)//減了以后M還有剩余{M-=V[j].num;//當前種類全部賣出 count+=V[j].income;//直接總價相加 j++;cout<<V[j].num;}else if(doubt<0) //不夠減這么多{count+=V[j].price*M;//剩余部分按照單價計算 break; } }cout<<"最高利潤值為："<<count<<endl;return 0;
}

????????仔細品味上述中的whlie循環：當M還不為0時——即還有需求量，就賣最貴的月餅。按順序一個一個賣：如果當前需求量足以賣完當前種類的全部數量，則直接累加總價；如果不足以賣完當前的全部，則有多少賣多少，按照單價計算即可~?

我們拿教材的測試用例測試一下：

3 20
18 15 10
75 72 45

結果為94.50，和標準答案一致~?

此外這里博主直接把排序寫在main函數了，寫在獨立的函數再調用，對于結構體型的vector好像有點bug，排序不太成功，大家如果知道原因的話可以在評論區寫出來~

二.區間貪心

題干如下：

對于這類題目，只需要牢記——優先選擇左端點大的區間！

下面來說說為什么要這樣做，如上圖：不難發現，為了保證盡可能多選，當某個較長的區間包含了較短的區間，我們肯定要先選擇最短的區間，這一點很好理解。

????????而對于上面這種情況，比如1和2這種重疊的區間，不難發現，如果選了左端點最大的1區間，只會占到9號位，而選了2號區間則會占到8號位——這顯然不符合貪心盡可能少花錢（少花區間）的思想，因此要選得盡可能靠左，這樣右邊空的會更多~如上，我們手算可以看出來最多有4個不相交的。?

教材上的代碼：?

#include <cstdio>
#include <algorithm>
using namespace std;const int maxn=110;
struct Inteval{int x,y;  //開區間左右端點 
}I[maxn]; bool cmp(Inteval a,Inteval b)
{if(a.x!=b.x)return a.x>b.x;   //左端點從大到小排序 elsereturn a.y<b.y;   //左端點相同的按右端點從小到大排序 
}int main() {int n;while(scanf("%d",&n,n!=0)){for(int i=0;i<n;i++)scanf("%d%d",&I[i].x,&I[i].y);sort(I,I+n,cmp); //排序區間 int ans=1,lastX=I[0].x;//ans記錄總數，lastX記錄上一個被選擇的區間的左端點 for(int i=1;i<n;i++){if(I[i].y<=lastX)   //如果該區間右端點在lastX左邊 {lastX=I[i].x;  //以I[i]作為新選中的區間 ans++;   //不相交的區間個數+1 }	}printf("%d\n",ans);	} return 0;
}

不過博主還是不太喜歡原始數組，下面給一種vector結構體版本：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct section{int x=0;int y=0;//x和y分別為左右端點 
}; int main() {int n=0;vector<section> V;cin>>n;for(int i=1;i<=n;i++) //讀入數據 {section temp;int x=0,y=0;cin>>x>>y;if(x>y)   //防止左端點大于右端點 {int temp1=x;x=y;y=temp1;	}else if(x==y) //若左右端點相同 {i-=1;  //則當前輸入 不算cout<<"不可以輸入相同的左右端點！"<<endl; continue;  //舍棄數據，本次循環作廢~ }	temp.x=x;temp.y=y;V.push_back(temp);}//按要求排序區間優先級 for(int i=0;i<=V.size()-1;i++){for(int j=i+1;j<=V.size()-1;j++){if(V[j].x>V[i].x)  //左端點越大越靠前{section temp=V[j];V[j]=V[i];V[i]=temp;}else if(V[j].x==V[i].x&&V[j].y<V[i].y) //左端點相同的話，右端點小的優先 {section temp=V[j];V[j]=V[i];V[i]=temp;} }}cout<<"順序如下："<<endl; for(int i=0;i<=V.size()-1;i++)cout<<V[i].x<<"~"<<V[i].y<<endl; int count=1,lastX=V[0].x;//count用來統計總數，lastX是上一個符合條件的區間的左端點for(int i=1;i<=V.size()-1;i++)//直接從第二個區間開始 {if(V[i].y<lastX)  //如果當前區間的右端點不和上一個左端點相加，滿足題意 {lastX=V[i].x;count++;}		} cout<<count<<endl;return 0;
}

測試如下：