貪心演算法

Part 1

貪心演算法簡介

貪心演算法是從某一個初始狀態出發，每次通過選取區域最優解向目標前進，并最終期望取得整體最優解的一種演算法，由這個定義可知，貪心選擇標準就是選擇“當前最好”的決策，貪心演算法根據這個標準進行決策，將原問題變成一個相似但規模更小的子問題，而后每一步選出來的一定是原問題整體最優解的一部分，

如果一個問題貪心后只剩下一個子問題且有最優子結構，那么該問題就可以使用貪心演算法，當一個問題的整體最優解包含其子問題的最優解時，我們稱次問題具有最優子結構性質，

Part 2

解題一般步驟

1、設計資料找規律；

2、進行貪心猜想；

3、正確性證明（包括列舉反例和嚴格的數學證明）；

4、程式實作，

Part 3

例題（洛谷P1080國王游戲）：

題目描述

恰逢 H國國慶，國王邀請n 位大臣來玩一個有獎游戲，首先，他讓每個大臣在左、右手上面分別寫下一個整數，國王自己也在左、右手上各寫一個整數，然后，讓這 n 位大臣排成一排，國王站在隊伍的最前面，排好隊后，所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數，然后向下取整得到的結果，

國王不希望某一個大臣獲得特別多的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣，所獲獎賞盡可能的少，注意，國王的位置始終在隊伍的最前面，

輸入格式

第一行包含一個整數n，表示大臣的人數，

第二行包含兩個整數 a和 b，之間用一個空格隔開，分別表示國王左手和右手上的整數，

接下來 n行，每行包含兩個整數a 和 b，之間用一個空格隔開，分別表示每個大臣左手和右手上的整數，

輸出格式

一個整數，表示重新排列后的隊伍中獲獎賞最多的大臣所獲得的金幣數，

輸入輸出樣例

說明/提示

【輸入輸出樣例說明】

按1、2、3 這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為 2；

按 1、3、2 這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為2；

按 2、1、3 這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為 2；

按2、3、1這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為9；

按 3、1、2這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為 2；

按3、2、1 這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為9，

因此，獎賞最多的大臣最少獲得 2個金幣，答案輸出 2，

【資料范圍】

對于 20%的資料，有 1≤ n≤ 10,0 < a,b < 8；

對于 40%的資料，有1≤ n≤20,0 < a,b < 8；

對于 60%的資料，有 1≤ n≤100；

對于 60%的資料，保證答案不超過 10^9；

對于 100%的資料，有 1 ≤ n ≤1,000,0 < a,b < 10000，

Part 4

解題思路

不妨先討論相鄰的二元組，由題意可知，相鄰兩個大臣交換位置不會對前面和后面的其他人的金幣數造成影響，也就是說相鄰兩人位置交換只會對這兩個人產生影響我們以此為切入點，分析調換相鄰的兩個人對答案的影響，

設這兩個人位置分別為i和i+1，左手數字為a[i]和a[i+1]，右手數字為b[i]和b[i+1]，兩人的金幣數為w[i]和w[i+1]，記 P[i]=a[1]*a[2]*a[3]*...*a[i]，

未調換順序時，k1=w[i]=P[i-1]/b[i]; k2=w[i+1]=P[i-1]*a[i]/b[i+1];則

ans1=max(k1,k2)

調換順序后k3=P[i-1]/b[i+1]; k4=P[i-1]*a[i+1]/b[i]; 則ans2=max(k3,k4)

顯然有k1<k4,k3<k2;如果ans1<ans2,那么必有k2<k4，化簡可得a[i]*b[i]<a[i+1]*b[i+1];

所以，為了ans取到最小值，我們需要將a[i]*b[i]較小的放在前面那么我們以a[i]*b[i]為關鍵字排序即可，同時，統計答案時一定不要忘了寫高精度，

小結

貪心演算法的核心問題是選擇能產生問題最優解的最優度量標準，即具體的貪心策略，

特點是快，在運行程序中無回溯程序，每一步都是當前的最佳選擇

演算法講解｜貪心演算法的理解與分析

Part 1

Part 2

Part 3

Part 4

小結

相關推薦：