在實際問題中，經常會遇到求一個問題的可行解和最優解的問題，這就是所謂的最優化問題，每個最優化問題都包含一組限制條件和一個優化函式，符合條件的解決方案稱為可行解，使優化函式取得最佳值的可行解稱為最優解，
貪心法是求解這類問題的一種常用演算法，它從問題的某一個初始解出發，采用逐步構造最優解的方法向給定的目標前進，
貪心法在每個區域階段，都做出一個看上去最優的決策（即某種意義下的、或某個標準下的區域最優解），并期望通過每次所做的區域最優選擇產生出一個全域最優解，
做出貪心決策的依據稱為貪心準則（策略），
想象這樣一個場景：一個小孩買了價值少于10元的糖，并將10元錢交給了售貨員，售貨員希望用數目最少的人民幣（紙幣或硬幣）找給小孩，假設提供了數目不限的面值為5元、2元、1元、5角以及1角的人民幣，售貨員應該這樣找零錢呢？售貨員會分步驟組成要找的零錢數，每次加入一張紙幣或一枚硬幣，選擇要找的人民幣時所采用的準則如下：每一次選擇應使零錢數盡量增大，為保證不多找，所選擇的人民幣不應使零錢總數超過最終所需的數目，
假設需要找給小孩6元7角，首先入選的是一張5元的紙幣，第二次入選的不能是5元或2元的紙幣，否則零錢總數將超過6元7角，第二次應選擇1元的紙幣（或硬幣），然后是一枚5角的硬幣，最后加入兩個1角的硬幣，
這種找零錢的方法就是貪心法，選擇要找的人民幣時所采用的準則就是采取的貪心標準（或貪婪策略），
貪心法（又稱貪婪演算法）是指在求最優解問題的程序中，依據某種貪心標準，從問題的初始狀態出發，通過若干次的貪心選擇而得出最優解或較優解的一種階梯方法，從貪心法“貪心”一詞便可以看出，在對問題求解時，貪心法總是做出在當前看來是最好的選擇，也就是說，貪心法不從整體最優上加以考慮，它所做出的僅是在某種意義上的區域最優解，
貪心法主要有以下兩個特點：
（1）貪心選擇性質：演算法中每一步選擇都是當前看似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未作出的選擇，
（2）最優子結構性質：演算法中每一次都取得了最優解（即區域最優解），要保證最后的結果最優，則必須滿足全域最優解包含區域最優解，
利用貪心法求解問題的一般步驟是：
（1）產生問題的一個初始解，
（2）回圈操作，當可以向給定的目標前進時，就根據區域最優策略，向目標前進一步，
（3）得到問題的最優解（或較優解），
實作該演算法的程式框架描述為：
從問題的某一初始解出發；
while （能朝給定總目標前進一步）
{
求出可行解的一個解元素；
}
由所有解元素組合成問題的一個可行解；
貪心法的優缺點主要表現在：
優點：一個正確的貪心演算法擁有很多優點，比如思維復雜度低、代碼量小、運行效率高、空間復雜度低等，
缺點：貪心法的缺點集中表現在他的“非完美性”，通常我們很難找到一個簡單可行并且保證正確的貪心思路，即使我們找到一個看上去很正確的貪心思路，也需要嚴格的正確性證明，這往往給直接使用貪心演算法帶來了較大的困難，
盡管貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題它能產生整體最優解或者是整體最優解的近似解，
【例1】租獨木舟
一群大學生到東湖水上公園游玩，在湖邊可以租獨木舟，各獨木舟之間沒有區別，一條獨木舟最多只能乘坐兩個人，且乘客的總重量不能超過獨木舟的最大承載量，為盡量減少游玩活動中的花銷，需要找出可以安置所有學生的最少的獨木舟條數，撰寫一個程式，讀入獨木舟的最大承載量、大學生的人數和每位學生的重量，計算并輸出要安置所有學生必須的最少的獨木舟條數，
（1）編程思路，
先將大學生按體重從大到小排好序，由于一條獨木舟最多只能乘坐兩個人，因此基于貪心法安排乘船時，總是找到一個當前體重最大的人，讓它盡可能與當前體重最小的人同乘一船，如此回圈直至所有人都分配完畢，即可統計出所需要的獨木舟數，
（2）源程式及運行結果，
#include <iostream>
using namespace std;
int main()
{
int maxweight,n,i,j,t,num;
int w[300];
cout<<"請輸入每條獨木舟的載重量和大學生的人數：";
cin>>maxweight>>n;
cout<<"請輸入每位學生的體重："<<endl;
for(i = 0; i < n; i++)
cin>>w[i];
for (i=0;i<n-1;i++) // 用冒泡排序法將體重按從大到小排序
for (j=0;j<n-i-1; j++)
if (w[j]<w[j+1])
{
t=w[j]; w[j]=w[j+1]; w[j+1]=t;
}
i = 0,num = 0;
while(i <= n-1)
{
if(w[i] + w[n -1] <= maxweight)
{
i++; n--; num++;
}
else
{
i++; num++;
}
}
cout<<"最少需要獨木舟"<<num<<"條，"<<endl;
return 0;
}
編譯并執行以上程式，得到如下所示的結果，
請輸入每條獨木舟的載重量和大學生的人數：100 12
請輸入每位學生的體重：
45 48 52 56 64 61 60 58 56 40 44 50
最少需要獨木舟8條，
Press any key to continue
需要特別注意的是，貪心法在求解最優化問題時，對大多數優化問題能得到最優解，但有時并不能求得最優解，
【例2】0/1背包問題
有一個容量為c的背包，現在要從n件物品中選取若干件裝入背包中，每件物品i的重量為w[i]、價值為p[i]，定義一種可行的背包裝載為：背包中物品的總重不能超過背包的容量，并且一件物品要么全部選取、要么不選取，定義最佳裝載是指所裝入的物品價值最高，并且是可行的背包裝載，
例如，設c= 12，n=4，w[4]={2，4，6，7}，p[4]={ 6，10，12，13}，則裝入w[1]和w[3]，最大價值為23，
- 問題分析
若采用貪心法來解決0/1背包問題，可能選擇的貪心策略一般有3種，每種貪心策略都是采用多步程序來完成背包的裝入，在每一步中，都是利用某種貪心準則來選擇將某一件物品裝入背包，
（1）選取價值最大者，
貪心策略為：每次從剩余的物品中，選擇可以裝入背包的價值最大的物品裝入背包，這種策略不能保證得到最優解，例如，設C=30，有3個物品A、B、C，w[3]={28，12，12}，p[3]={30，20，20}，根據策略，首先選取物品A，接下來就無法再選取了，此時最大價值為30，但是，選取裝B和C，最大價值為40，顯然更好，
（2）選取重量最小者，
貪心策略為：從剩下的物品中，選擇可以裝入背包的重量最小的物品裝入背包，其想法是通過多裝物品來獲得最大價值，這種策略同樣不能保證得到最優解，它的反例與第（1）種策略的反例差不多，
（3）選取單位重量價值最大者
貪心策略為：從剩余物品中，選擇可裝入背包的p[i]/w[i]值最大的物品裝入，這種策略還是不能保證得到最優解，例如，設C=40，有3個物品A、B、C，w[3]={15，20，28}，p[3]={15，20，30}，按照策略，首先選取物品C（p[2]/w[2]>1），接下來就無法再選取了，此時最大價值為30，但是，選取裝A和B，最大價值為35，顯然更好，
由上面的分析可知，采用貪心法并不一定可以求得最優解，學習了動態規劃演算法后，這個問題可以得到較好的解決，采用動態規劃撰寫的源程式及運行結果如下，
#include <iostream>
#include <iomanip>
using namespace std;
#define N 50
int main()
{
int p[N],w[N],m[N][5*N];
int i,j,c,cw,n,sw,sp;
cout<<"請輸入 n 值:"; cin>>n;
cout<<"請輸入背包容量："; cin>>c;
cout<<"請依次輸入每種物品的重量：";
for (i=1;i<=n;i++)
cin>>w[i];
cout<<"請依次輸入每種物品的價值：";
for (i=1;i<=n;i++)
cin>>p[i];
for (j=0;j<=c;j++) // 首先計算邊界條件m[n][j]
if (j>=w[n])
m[n][j]=p[n];
else
m[n][j]=0;
for(i=n-1;i>=1;i--) // 逆推計算m[i][j] （i從n-1到1）
for(j=0;j<=c;j++)
if(j>=w[i] && m[i+1][j]<m[i+1][j-w[i]]+p[i])
m[i][j]= m[i+1][j-w[i]]+p[i];
else
m[i][j]=m[i+1][j];
cw=c;
cout<<"背包所裝物品如下："<<endl;
cout<<" i w(i) p(i) "<<endl;
cout<<"----------------------"<<endl;
for(sp=0,sw=0,i=1;i<=n-1;i++) // 以表格形式輸出結果
if(m[i][cw]>m[i+1][cw])
{
cw-=w[i];sw+=w[i];sp+=p[i];
cout<<setw(3)<<i<<setw(8)<<w[i]<<setw(8)<<p[i]<<endl;
}
if(m[1][c]-sp==p[n])
{
sw+=w[n];sp+=p[n];
cout<<setw(3)<<n<<setw(8)<<w[n]<<setw(8)<<p[n]<<endl;
}
cout<<"裝載物品重量為 "<<sw<<" , 最大總價值為 "<<sp<<endl;
return 0;
}
編譯并執行以上程式，得到如下所示的結果，
請輸入 n 值:6
請輸入背包容量：60
請依次輸入每種物品的重量：15 17 20 12 9 14
請依次輸入每種物品的價值：32 37 46 26 21 30
背包所裝物品如下：
i w(i) p(i)
----------------------
2 17 37
3 20 46
5 9 21
6 14 30
裝載物品重量為 60 , 最大總價值為 134
Press any key to continue
【例3】取數游戲
給出2n個（n<=100）個自然數，游戲雙方分別為A方（計算機方）和B方（對弈的人），只允許從數列兩頭取數，A先取，然后雙方依次輪流取數，取完時，誰取得的數字總和最大即為取勝方；若雙方的和相等，屬于A勝，試問A方可否有必勝的策略？
（1）編程思路，
設n=4時，8個自然數的序列為：7 10 3 6 4 2 5 2，
若設計這樣一種原始的貪心策略：讓A每次取數列兩頭較大的那個數，由于游戲者也不會傻，他也會這么干，所以，在上面的數列中，A方會順序取7、3、4、5，B方會順序取10、6、2、2，由此得出：A方取得的數和為7+3+4+5=19，B方取得的數和為10+6++2+2=20，按照規則，判定A方輸，
因此，如果按上述的貪心策略去玩這個游戲，A并沒有必勝的保證，仔細觀察游戲程序，可以發現一個事實：由于是2n個數，A方取走偶位置上的數以后，剩下兩端數都處于奇位置；反之，若A方取走的是奇位置上的數，則剩下兩端的數都處于偶位置，
也就是說，無論B方如何取法，A方既可以取走奇位置上的所有數，也可以取走偶位置上的所有數，
由此，可以得出一種有效的貪心策略：若能夠讓A方取走“數和較大的奇（或偶）位置上的所有數”，則A方必勝，這樣，取數問題便對應于一個簡單的問題了：讓A方取奇偶位置中數和較大的一半數，
程式中用陣列a存盤2*n個自然數的序列，先求出奇數位置和偶數位置的數和sa及sb，設定tag為A取數的奇偶位置標志，tag=0表示偶位置數和較大，A取偶位置上的所有數；tag=1表示奇位置上的數和較大，A取奇位置上的所有數，
lp、rp為序列的左端位置和右端位置；ch為輸入的B方取數的位置資訊（L或R），
（2）源程式及運行結果，
#include <iostream>
using namespace std;
int main()
{
int a[201],n,i,sa,sb,tag,t,lp,rp;
char ch;
cout<<"請輸入 n 的值：";
cin>>n;
cout<<"請依次輸入 "<<2*n<<" 個自然數："<<endl;
for (i=1;i<=2*n;i++)
cin>>a[i];
sa=sb=0;
for(i=1;i<=n;i++)
{
sa=sa+a[2*i-1];
sb=sb+a[2*i];
}
if (sa>=sb) tag=1;
else { tag=0; t=sa; sa=sb; sb=t; }
lp = 1; rp = 2*n;
for(i=1;i<=n;i++) // A方和B方依次進行n次對弈
{
if ((tag==1 && lp % 2==1) || (tag==0 && lp % 2 == 0))
// 若A方應取奇位置數且左端位置為奇，或者A方應取得偶位置數且
// 左端位置為偶，則A方取走左端位置的數
{ cout<<" A方左端取數 "<<a[lp]; lp = lp + 1; }
else
{ cout<<" A方右端取數 "<<a[rp]; rp = rp - 1; }
do {
cout<<" B方取數，輸入L（取左邊的數）或R（取右邊的數）："; cin>>ch;
if (ch =='L' || ch=='l')
{ cout<<" B方左端取數 "<<a[lp]<<endl; lp = lp + 1; }
if (ch == 'R' || ch=='r')
{ cout<<" B方右端取數 "<<a[rp]<<endl; rp = rp - 1; }
} while (!(ch == 'L' || ch =='R' || ch=='l' || ch=='r'));
}
cout<<" A方取數的和為 "<<sa<<" ，B方取數的和為"<<sb<<endl;
return 0;
}
編譯并執行以上程式，得到如下所示的結果，
請輸入 n 的值：4
請依次輸入 8 個自然數：
7 10 3 6 4 2 5 2
A方右端取數 2 B方取數，輸入L（取左邊的數）或R（取右邊的數）：L
B方左端取數 7
A方左端取數 10 B方取數，輸入L（取左邊的數）或R（取右邊的數）：L
B方左端取數 3
A方左端取數 6 B方取數，輸入L（取左邊的數）或R（取右邊的數）：R
B方右端取數 5
A方右端取數 2 B方取數，輸入L（取左邊的數）或R（取右邊的數）：L
B方左端取數 4
A方取數的和為 20 ，B方取數的和為19
Press any key to continue
【例4】刪數問題
從鍵盤輸入一個高精度正整數num（num不超過200位，且不包含數字0），任意去掉S個數字后剩下的數字按原先后次序將組成一個新的正整數，撰寫一個程式，對給定的num和s，尋找一種方案，使得剩下的數字組成的新數最小，
例如，輸入：51428397 5，輸出：123，
（1）編程思路，
由于鍵盤輸入的是一個高精度正整數num（num不超過200位，且不包含數字0），因此用字串陣列來進行存盤，
為了盡可能地逼近目標，選取的貪心策略為：每一步總是選擇一個使剩下的數最小的數字刪去，即按高位到低位的順序搜索，若各位數字遞增，則洗掉最后一個數字，否則洗掉第一個遞減區間的首字符，然后回到串首，按上述規則再洗掉下一個數字，重復以上程序s次，剩下的數字串便是問題的解了，
也就是說，刪數問題采用貪心演算法求解時，采用最近下降點優先的貪心策略：即x1<x2<…<xi<xj；如果xk<xj，則刪去xj，得到一個新的數且這個數為n-1位中為最小的數Nl，可表示為x1x2…xixkxm…xn，對N1而言，即刪去了1位數后，原問題T變成了需對n-1位數刪去k-1個數的新問題T′，新問題和原問題相同，只是問題規模由n減小為n-1，刪去的數字個數由k減少為k-1，基于此種洗掉策略，對新問題T′，選擇最近下降點的數進行洗掉，如此進行下去，直至刪去k個數為止，
（2）源程式及運行結果，
#include<iostream>
using namespace std;
int main()
{
char num[200]={'\0'};
int times,i,j;
cout<<"Please input the number:";
cin>>num;
cout<<"input times:";
cin>>times;
while(times>0) // 回圈times，每次洗掉一個數字
{
i=0; // 每次洗掉后從頭開始搜尋待洗掉數字
while (num[i]!='\0' && num[i]<=num[i+1])
i++;
for(j=i;j<strlen(num);j++)
num[j]=num[j+1]; // 將位置i處的數字洗掉
times--;
}
cout<<"Result is "<<num<<endl;
return 0;
}
編譯并執行以上程式，得到如下所示的結果，
Please input the number:1235498673214
input times:5
Result is 12343214
Press any key to continue
【例5】過河問題
在一個月黑風高的夜晚，有一群旅行者在河的右岸，想通過唯一的一根獨木橋走到河的左岸，在這伸手不見五指的黑夜里，過橋時必須借助燈光來照明，不幸的是，他們只有一盞燈，另外，獨木橋上最多承受兩個人同時經過，否則將會坍塌，每個人單獨過橋都需要一定的時間，不同的人需要的時間可能不同，兩個人一起過橋時，由于只有一盞燈，所以需要的時間是較慢的那個人單獨過橋時所花的時間，現輸入n（2≤n<100）和這n個旅行者單獨過橋時需要的時間，計算總共最少需要多少時間，他們才能全部到達河的左岸，
例如，有3個人甲、乙、丙，他們單獨過橋的時間分別為1、2、4，則總共最少需要的時間為7，具體方法是：甲、乙一起過橋到河的左岸，甲單獨回到河的右岸將燈帶回，然后甲、丙再一起過橋到河的左岸，總時間為2+1+4=7，
（1）編程思路，
假設n個旅行者的過橋時間分別為t[0]、t[1]、t[2]、…、t[n-1]（已按升序排序），n個旅行者過橋的最快時間為sum，
從簡單入手，如果n= 1，則sum =t[0]；如果n = 2，則sum = t[1]；如果n = 3，則sum = t[0]+t[1]+t[2]，如果n > 3，考慮將單獨過河所需要時間最多的兩個人送到對岸去，有兩種方式：
1）最快的（即所用時間t[0]）和次快的（即所用時間t[1]）過河，然后最快的將燈送回來；之后次慢的（即所用時間t[N-2]）和最慢的（即所用時間t[N-1]）過河，然后次快的將燈送回來，
2）最快的和最慢的過河，然后最快的將燈送回來；之后最快的和次慢的過河，然后最快的將燈送回來，
這樣就將過河所需時間最大的兩個人送過了河，而對于剩下的人，采用同樣的處理方式，接下來做的就是判斷怎樣用的時間最少，
方案1）所需時間為：t[0]+2*t[1]+t[n-1]
方案2）所需時間為：2*t[0]+t[n-2]+t[n-1]
如果方式1）優于方式2），那么有t[0]+2*t[1]+t[n-1]<2*t[0]+t[n-2]+t[n-1] 化簡得2*t[1]<t[0]+t[n-2]
即此時只需比較2*t[1]與t[0]+t[n-2]的大小關系即可確定最小時間，此時已經將單獨過河所需時間最多的兩個人送過了河，那么剩下過河的人數為n=n-2，采取同樣的處理方式，
（2）源程式及運行結果，
#include <iostream>
using namespace std;
int main()
{
int n,t[100],i,sum,t1,t2;
cout<<"請輸入需要過河的人數：";
cin>>n;
cout<<"請按升序排列的順序依次輸入每人過河的時間："<<endl;
for (i=0;i<n;i++)
cin>>t[i];
if (n==1) // 一個人過河
sum=t[0];
else // 多個人過河
{
sum = 0;
while(1)
{
if(n == 2) // 剩兩個人
{
sum += t[1];
break;
}
else if(n == 3) // 剩三個人
{
sum += t[0] + t[1] + t[2];
break;
}
else
{
t1 = t[0] + t[1] + t[1] + t[n-1]; // 方案1
t2 = t[0] + t[0] + t[n-1] + t[n-2]; // 方案2
sum += (t1 > t2 ? t2 : t1);
n -= 2;
}
}
}
cout<<"最少需要的時間為："<<sum<<endl;
return 0;
}
編譯并執行以上程式，得到如下所示的結果，
請輸入需要過河的人數：5
請按升序排列的順序依次輸入每人過河的時間：
1 2 4 5 10
最少需要的時間為：22
Press any key to continue
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/345470.html
標籤：C++
上一篇：當它們回傳null/none時，我如何為刮取的結果設定默認值
下一篇：C++實作一個SOAP客戶端