貪婪演算法(Greedy)
概念
在每一步採用當前看起來最好的選擇，進而希望使最終答案最好的方法
想想看
上圖的植物要如何吃到最多隻蟲? 從最近的蟲開始吃? 從一口氣能吃到最多蟲的地方開始吃?
雜談
Greedy可以說是在日常生活中，最常看見應用例子的演算法。
使用Greedy之前，要先想清楚每一步都採用當前看起來最好的選擇，真的能使最終答案最好嗎?
範例1 - 換錢
在銀行提款時，常常會拿到以最少紙鈔、硬幣組成的現金
要怎麼才能 n 元以最少的紙鈔、硬幣組成呢?
新台幣常用的紙鈔、硬幣有以下幾種：
- 1元
- 5元
- 10元
- 50元
- 100元
- 500元
- 1000元
[input]
552
1246
10000
[output]
552=500*1 50*1 1*2
1246=1000*1 100*2 10*4 5*1 1*1
10000=1000*10
[想法]
用面額較大的紙鈔或硬幣，可以減少全部紙鈔和硬幣的數量
因此優先換面額較大的紙鈔或硬幣，換完才換較小的
[code]
#include<iostream>
using namespace std;
int main()
{
int money[7];
money[0] = 1000;
money[1] = 500;
money[2] = 100;
money[3] = 50;
money[4] = 10;
money[5] = 5;
money[6] = 1;
int n, i;
while( cin >> n )
{
cout << n << "=";
for( i=0 ; i<=6 ; i++ )
{
if( n >= money[i] )
{
// $1000 * 幾張
cout << money[i] << "*" << n/money[i] << " ";
n = n%money[i];
}
}
cout << endl;
}
return 0;
}
自我思考
- 如果新台幣加入一種新硬幣 23元 ，greedy法還會成立嗎?
範例2 - UVA Q12405 Scarecrow(稻草人)
點 ( . ) 表示良田，井號 ( # ) 表示不毛之地，一隻稻草人可以保護3格良田，下圖的要插3隻稻草人。
...##....##
[想法]
一開始沒放置稻草人時，所有地都沒被保護到
運算後，所有的好地一定要被稻草人保護到
由左往右看田地，一發現有好地沒被保護到，就放一個稻草人在此好地的右邊一格
該稻草人除了保護此地，還有機會保護到右邊一格和右邊兩格的好地
[code]
#include<iostream>
using namespace std;
int main()
{
int T; //測資數量
int N; //農田的長度
int ans; //答案
int Ti, i;
char farmland[100]; //農田
bool ok[100]; //農田有無被保護，true代表有受到保護
while( cin >> T )//輸入測資數量
{
for(int Ti=1 ; Ti<=T ; Ti++ )
{
cin >> N >> farmland;
//[initial][初始化]
ans = 0;
for( i=0 ; i<N ; i++ )
{
ok[i] = false; //還沒放置稻草人，預設每個農田都會被烏鴉攻擊
}
//[greedy][貪婪演算法]
for( i=0 ; i<N ; i++ )
{
if( farmland[i] == '.' and ok[i] == false ){ //'目前的地圖是可以耕耘的農田' and '沒有受到稻草人保護'
//put a new scarecrow
ans++; //放了一隻稻草人，稻草人數量+1
ok[i] = true; //稻草人所在地的左方農田
ok[i+1] = true; //稻草人所在地的農田
ok[i+2] = true; //稻草人所在地的右方農田
}
}
//[output]
cout << "Case " << Ti << ": " << ans << endl;
}
}
return 0;
}