C++與演算法

貪婪演算法(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] )
            {
                cout << money[i] << "*" << n/money[i] << " ";
                n = n%money[i];
            }
        }
        cout << endl;
    }

    return 0;
}

自我思考

  • 如果新台幣加入一種新硬幣 23元，greedy法還會成立嗎?



範例2 - UVA Q12405 Scarecrow

http://luckycat.kshs.kh.edu.tw/homework/q12405.htm

[想法]

一開始沒放置稻草人時，所有地都沒被保護到

運算後，所有的好地一定要被稻草人保護到


由左往右看田地，一發現有好地沒被保護到，就放一個稻草人在此好地的右邊一格

該稻草人除了保護此地，還有機會保護到右邊一格和右邊兩格的好地

[code]

#include<iostream>
using namespace std;

int main()
{
    int T, N, ans;
    int Ti, i;
    char map[105];
    bool ok[105];

    while( cin >> T )
    {
        for( Ti=1 ; Ti<=T ; Ti++ )
        {
            cin >> N >> map;

            //[initial]
            ans = 0;
            for( i=0 ; i<N ; i++ )
            {
                ok[i] = false;
            }

            //[greedy]
            for( i=0 ; i<N ; i++ )
            {
                if( map[i] == '.' and ok[i] == false )
                {
                    //put a new scarecrow
                    ans++;
                    ok[i] = true;
                    ok[i+1] = true;
                    ok[i+2] = true;
                }
            }

            //[output]
            cout << "Case " << Ti << ": " << ans << endl;
        }
    }

    return 0;
}



延伸閱讀



題目練習