向日葵朝著太陽轉動，時刻追求自身成長的最大可能。

貪心策略在一輪輪的簡單選擇中，逐步導向最佳答案。

課堂學習

引入

貪心算法（英語：greedy algorithm），是用計算機來模擬一個「貪心」的人做出決策的過程。這個人十分貪婪，每一步行動總是按某種指標選取最優的操作。而且他目光短淺，總是只看眼前，并不考慮以后可能造成的影響。

可想而知，并不是所有的時候貪心法都能獲得最優解，所以一般使用貪心法的時候，都要確保自己能證明其正確性。

解釋

適用范圍

貪心算法在有最優子結構的問題中尤為有效。最優子結構的意思是問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。1

證明

貪心算法有兩種證明方法：反證法和歸納法。一般情況下，一道題只會用到其中的一種方法來證明。

1. 反證法：如果交換方案中任意兩個元素/相鄰的兩個元素后，答案不會變得更好，那么可以推定目前的解已經是最優解了。
2. 歸納法：先算得出邊界情況（例如?）的最優解?，然后再證明：對于每個?，?都可以由??推導出結果。

要點

常見題型

在提高組難度以下的題目中，最常見的貪心有兩種。

• 「我們將 XXX 按照某某順序排序，然后按某種順序（例如從小到大）選擇。」。
• 「我們每次都取 XXX 中最大/小的東西，并更新 XXX。」（有時「XXX 中最大/小的東西」可以優化，比如用優先隊列維護）

二者的區別在于一種是離線的，先處理后選擇；一種是在線的，邊處理邊選擇。

排序解法

用排序法常見的情況是輸入一個包含幾個（一般一到兩個）權值的數組，通過排序然后遍歷模擬計算的方法求出最優值。

后悔解法

思路是無論當前的選項是否最優都接受，然后進行比較，如果選擇之后不是最優了，則反悔，舍棄掉這個選項；否則，正式接受。如此往復。

區別

與動態規劃的區別

貪心算法與動態規劃的不同在于它對每個子問題的解決方案都做出選擇，不能回退。動態規劃則會保存以前的運算結果，并根據以前的結果對當前進行選擇，有回退功能。

小結

• 貪心算法通常用于解決最優化問題，其原理是在每個決策階段都做出局部最優的決策，以期獲得全局最優解。
• 貪心算法會迭代地做出一個又一個的貪心選擇，每輪都將問題轉化成一個規模更小的子問題，直到問題被解決。
• 貪心算法不僅實現簡單，還具有很高的解題效率。相比于動態規劃，貪心算法的時間復雜度通常更低。
• 在零錢兌換問題中，對于某些硬幣組合，貪心算法可以保證找到最優解；對于另外一些硬幣組合則不然，貪心算法可能找到很差的解。
• 適合用貪心算法求解的問題具有兩大性質：貪心選擇性質和最優子結構。貪心選擇性質代表貪心策略的有效性。
• 對于某些復雜問題，貪心選擇性質的證明并不簡單。相對來說，證偽更加容易，例如零錢兌換問題。
• 求解貪心問題主要分為三步：問題分析、確定貪心策略、正確性證明。其中，確定貪心策略是核心步驟，正確性證明往往是難點。
• 分數背包問題在 0-1 背包的基礎上，允許選擇物品的一部分，因此可使用貪心算法求解。貪心策略的正確性可以使用反證法來證明。
• 最大容量問題可使用窮舉法求解，時間復雜度為??O(n2)。通過設計貪心策略，每輪向內移動短板，可將時間復雜度優化至?O(n)。
• 在最大切分乘積問題中，我們先后推理出兩個貪心策略：≥4?的整數都應該繼續切分，最優切分因子為?3?。代碼中包含冪運算，時間復雜度取決于冪運算實現方法，通常為?0(1)或O(logn)。

課堂訓練

2909?貪心的小童?

描述

兔子采集隊工作回來，把采集回來的胡蘿卜分成 4 堆,小童只能從每堆里拿走 1 根胡蘿卜。
小童的目標是拿走總重量最重的 4 根胡蘿卜。假如我們知道每根胡蘿卜的重量，愛學編程的你來幫幫小童吧。

輸入描述

4堆胡蘿卜，共4行：每行第一個正整數n，是一堆胡蘿卜的數量（≤1000）。后面n個正整數，是每堆胡蘿卜中每個胡蘿卜的重量（1≤單個胡蘿卜重≤100）。

輸出描述

請問拿走的4根胡蘿卜總重量最大是多少？

樣例輸入 1?

5 4 3 2 1 6
4 3 2 1 4
6 9 3 2 4 6 3
3 11 2 1

樣例輸出 1?

30

#include <bits/stdc++.h>
using namespace std;
int a[1001],n,sum=0;
int main(){for(int i=1;i<=4;i++){cin>>n;int t=0; //定義一個變量，存儲每堆胡蘿卜重量的最大值。for(int j=1;j<=n;j++){cin>>a[j]; //輸入胡蘿卜的重量//胡蘿卜的重量大于t，就更新t的值。求出每一堆的最優結果。if(a[j]>t) t=a[j];}sum+=t; //累加每堆最重胡蘿卜的重量，得到最終的最優結果。}cout<<sum<<endl;return 0;
}

2910?士兵突擊

描述

森林戰爭中兔子們決定越過一個無人防守的湖泊偷襲敵人。一共n名士兵，輸入每名士兵的體重。只有一艘船，船的載重量一定（需要輸入）。只能運輸一次，要求能裝載最多的士兵，最多能運送多少名士兵？

輸入描述

共兩行：
第一行輸入兩個整數，士兵數量和船載重量（小于2000）。
第二行，輸入每名士兵的體重（體重<300）。

輸出描述

共1行，最多裝載多少名士兵。

樣例輸入 1?

5 11
7 2 6 4 5

樣例輸出 1?

3

#include <bits/stdc++.h>
using namespace std;
int main() {//定義變量和數組int n,c,w[2001]= {};//輸入士兵個數n和船載重量cin>>n>>c;//輸入n個士兵兔體重for(int i=0; i<n; i++)cin>>w[i];//按照體重升序排序sort(w,w+n);//tmp計算上船的總體重ans數量int tmp=0,ans=0;for(int i=0; i<n; i++) {//從體重最小士兵開始依次上船tmp+=w[i];//上船士兵兔總重量小于載重量if(tmp<=c)ans++;  //統計士兵數量elsebreak;  //否則終止循環}cout<<ans;return 0;
}

4454?上船問題

描述

有?n?個人，需要過河，第?i?個人的體重為wi，河邊有很多船，每艘船的最大載重為m且最多可以上兩個人，問最少需要多少艘船。

輸入描述

第一行輸入兩個整數?n?和?m，表示人數和船的載重。
第二行?n?個整數，用空格隔開，表示體重。

輸出描述

一個整數，表示需要的最少船只。

樣例輸入 1?

6 120
15 17 102 70 90 68

樣例輸出 1?

4

提示

數據范圍與提示

1≤n,m≤200，1≤wi?≤100，wi?≤m

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[201];
int main()
{//n為人數，m為一條船的最大承重cin>>n>>m;//輸入體重for(int i=1;i<=n;i++) cin>>a[i];//體重從小到大排序sort(a+1,a+n+1);//i表示最輕體重下標位置，j表示最重體重下標位置int i=1,j=n;//記錄所用船數int cnt=0;//遍歷所有船員while(i<=j){//判斷最輕和最重船員是否超過載重if(a[i]+a[j]>m) {j--;//超過載重就選擇更輕的船員cnt++;//記錄船的數量}else{//切換下一組最輕、最終i++;j--;cnt++;//記錄船的數量}}//輸出最終解cout<<cnt<<endl;	return 0;
}

2908?節省時間

描述

童程學校的信息奧賽課非常受歡迎。每次午休，學生們都要排隊找IT龍老師答疑。有的同學問題簡單，答疑時間短。有的同學問題難，答疑時間長。IT龍老師想到了一個辦法，讓助理老師對每個學生的問題預估一個答疑時長，寫成小條給IT龍老師。請你編程幫助IT龍老師，找到一種排隊順序，讓同學們的平均答疑完成時間最少（結果保留兩位小數）。注意：答疑完成時間=自己的答疑時間+等前面同學的時間。

輸入描述

第一行，輸入答疑學生數量（學生數量≤1000）。
第二行，助理老師預估的每個學生的答疑時長（時長≤2000 單位分鐘）。

輸出描述

平均答疑完成時間最少。

樣例輸入 1?

4
3 1 2 6

樣例輸出 1?

5.50

#include <bits/stdc++.h>
using namespace std;
int a[1001],n;
int main(){cin>>n;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);//按照答疑時間升序排序int s=0;for(int i=0;i<n;i++){//第1個人的答疑時間乘以n,等于自己的答疑時間和后面人的等待時間  s+=(n-i)*a[i];//計算所有人的總時間}printf("%.2f",s*1.0/n);return 0;
} 

4453?購物競賽

描述

某大型賣場在節日期間舉行購物競賽，參賽者可以推著購物車在賣場中選擇提前羅列好的商品，可選商品有?N?種，每種商品的總價為?M?元，被拆分成均等的?K?個包裝，現在購物車里可以裝的包裝數量被固定為?L?個，問怎么選才能使購物車中的價值最大。

輸入描述

第一行輸入整數?N?和?L，用空格隔開。
第二行到第 N+1 行，每行兩個整數?M?和?K，用空格隔開。

輸出描述

一個整數，購物車中可以裝載的最大價值。

樣例輸入 1?

5 10
12 6
8 2
20 4
7 7
15 5

樣例輸出 1?

40

提示

數據范圍與提示

1≤N,L≤100，1≤M,K≤100，M%K=0

#include<bits/stdc++.h>
using namespace std;
//創建表示商品屬性的結構體
struct cmdt{int price, num, ave;
}box[110];
//排序規則-單價從大到小排序
bool cmp(cmdt x, cmdt y) {return x.ave>y.ave;
}
int main() {int n=0, l=0, sum=0;cin>>n>>l;for (int i=0; i<n; i++) {//輸入商品價值及數量cin>>box[i].price>>box[i].num;//計算商品單價box[i].ave=box[i].price/box[i].num;}//按照單價從大到小排序sort(box, box+n, cmp);//遍歷商品種類for (int i=0; i<n; i++) {//當前商品價值全部累加if (box[i].num<l) {sum+=box[i].price;l-=box[i].num;//當前商品價值部分累加} else {sum+=box[i].ave*l;break;}}cout<<sum;return 0;
}

課后作業

2381?可可島的寶藏

描述

可可島位于距哥斯達黎加海岸300英里的海中，曾是17世紀海盜的休息站，海盜們將掠奪的財寶在此裝裝卸卸，埋埋藏藏，為這個無名小島平添了神秘色彩，據說島上至少埋有6處寶藏。某天童童歷經千難萬險到了可可島上，上面有許多珍貴的金屬，童童雖然更喜歡各種寶石的藝術品，可是也不拒絕這樣珍貴的金屬。但是他只帶著一個口袋，口袋至多只能裝重量為w的物品。島上金屬有 s 個種類, 每種金屬重量不同，分別為 n1,n2,…,ns，同時每個種類的金屬總的價值也不同，分別為 v1,v2, …, vs。童童想一次帶走價值盡可能多的金屬，問他最多能帶走價值多少的金屬。注意到金屬是可以被任意分割的，并且金屬的價值和其重量成正比。

數據范圍與提示：
1≤w≤10000，1≤s≤100，1≤ni≤10000，1≤vi≤10000

輸入描述

第1行是測試數據的組數 k，后面跟著 k 組輸入。
每組測試數據占3行，第 1 行是一個正整數 w(1≤w≤10000)，表示口袋承重上限。
第 2 行是一個正整數 s(1≤s≤100) ，表示金屬種類。
第 3 行有 2s 個正整數，分別為n1,v1,n2,v2,…,ns,vs分別為第一種，第二種，…，第 s 種金屬的總重量和總價值 (1≤ni≤10000,1≤vi≤10000)。

輸出描述

k 行，每行輸出對應一個輸入。輸出應精確到小數點后 2 位。

樣例輸入 1?

2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43

樣例輸出 1?

171.93
508.00

提示

數據范圍與提示：
1≤w≤10000，1≤s≤100，1≤ni≤10000，1≤vi≤10000

#include<bits/stdc++.h>
using namespace std;
struct node{//結構體存儲重量和價值int wei,v;//用來存儲單位價值double p;
}b[210];
int k,w,s;
bool my_cmp(node x,node y){return x.p>y.p;}//按照單位價值降序排序
int main(){cin>>k;//輸入k組數據while(k--){cin>>w>>s;double sum=0;//在while循環里面初始化for(int i=1;i<=s;i++){cin>>b[i].wei>>b[i].v;b[i].p=b[i].v*1.0/b[i].wei;//計算單位價值}//排序sort(b+1,b+s+1,my_cmp);for(int i=1;i<=s;i++){if(w-b[i].wei>=0){//能裝入w-=b[i].wei;//裝入，減去物品重量sum+=b[i].v;//計算裝入物品的價值}else{//不能裝入sum+=w*b[i].p;//裝一部分break;//終止循環}}printf("%.2f\n",sum);//輸出一定要加換行}return 0;
} 

1547?童程同學講禮貌

描述

童程學校的學生非常遵守學校的規章制度。小朋友們課間喝水，都去排隊打水，但是條件很有限，只有一臺飲水機。為了珍惜有限的課余時間，老師想到了一個辦法，讓同學們的平均等待時間最少。現在有 n 個小朋友在一個飲水機前排隊接水，假如每個人接水的時間為 Ti，請你編程幫老師找出這 n 個小朋友排隊的一種順序，使得 n 個人的平均等待時間最小。(需要考慮自己打水的時間)

輸入描述

輸入文件共兩行，第一行為 n，1≤n≤1000
第二行分別表示第 1 個同學到第 n 個同學每人的接水時間 T1，T2，…，Tn，每個數據之間有 1 個空格，0<Ti≤1000。

輸出描述

輸出文件有一行，為老師得到的某種排列方案下的最小平均等待時間(輸出結果精確到小數點后兩位)。

樣例輸入 1?

10                                    
56 12 1 99 1000 234 33 55 99 812

樣例輸出 1?

532.00

提示

數據范圍與提示：
1≤n≤1000，0<Ti≤1000。

#include<bits/stdc++.h>
using namespace std;
int a[1010],n;
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//按照打水時間排序sort(a+1,a+n+1);int s=0;for(int i=1;i<=n;i++){//計算等待時間s+=(n-i+1)*a[i];}printf("%.2f",s*1.0/n);return 0;
}

4458?分配禮物

描述

有?n?件禮物，第?i?件禮物的價值為?wi?，需要給這些禮物進行分組，每組禮物數量不能超過?2、價值不能超過?y，要求組數盡量少，每位同學可以領一組禮物領完為止，問有多少同學領到兩個禮物。

輸入描述

第一行兩個整數?n、y，用空格隔開。
第二行?n?個整數，用空格隔開，表示禮物的價值。

輸出描述

一個整數，表示獲得兩個禮物的人數。

樣例輸入 1?

5 36
12 35 20 2 25

樣例輸出 1?

2

提示

數據范圍與提示

1≤n,y≤100，1≤wi?≤100，wi≤y

#include<bits/stdc++.h>
using namespace std;
int main(){int a[105]={};int n,y;cin>>n>>y;for(int i=1;i<=n;i++)	cin>>a[i];sort(a+1,a+n+1);  //按禮物價值升序int i=1,j=n; //i表示價值最小禮物 j表示價值最大禮物int two=0; //表示兩個禮物一組的組數while(i<j){if(a[i]+a[j]>y) //價值和超過y，價值高的自己1組 j--;else{ //沒有超過y，兩個禮物放1組i++;j--;two++;}}cout<<two;return 0;
}

1743?童童看節目

描述

寒假到了，童童終于可以開心的看電視節目了。寒假播放的少兒節目太多了，童童想盡量多的看到這些節目，但是童童有個習慣，他只看完整的節目。
現在他把他喜歡的電視節目的轉播時間表給你，你能幫他合理安排嗎？

數據范圍與提示：
n≤100

輸入描述

輸入包含多組測試數據。每組輸入的第一行是一個整數 n（n≤100），表示童童給你的節目表上節目的總數。
接下來 n 行，每行輸入兩個整數 si?和 ei（1≤i≤n，表示第 i 個節目的開始和結束時間，為了簡化問題，每個時間都用一個正整數表示。
當 n=0 時，輸入結束。

輸出描述

對于每組輸入，輸出能完整看到最多多少個節目。

樣例輸入 1?

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
5
1 5
2 6
5 8
7 13
9 12
0

樣例輸出 1?

5
3

#include<bits/stdc++.h>
using namespace std;
struct Node{int s;int e;
};
Node a[105];
bool cmp(Node x,Node y){if(x.e!=y.e)	return x.e<y.e;else	return x.s<y.s;
}
int main(){int n;cin>>n;while(n!=0){ //n不等于0就繼續for(int i=1;i<=n;i++)cin>>a[i].s>>a[i].e;sort(a+1,a+n+1,cmp); //結束時間早的在前int s=1;//統計節目數量，默認第1可以看Node t=a[1];//t記錄已統計的最后1個節目for(int i=2;i<=n;i++){//當前節目開始時間不小于t的結束時間if(a[i].s>=t.e){s++;t=a[i];}}cout<<s<<endl;cin>>n; //輸入下1組n，如果n=0則退出while}return 0;
}