WHALEon120.github.io

貪心法則

回前頁

原理

保證在每次選擇極端值進行運算後，能得到最佳解。
優點為複雜度低，程式碼簡單
缺點為不一定正確

舉例

1.錢包問題

題目概念:
再買東西時要找k元，請問最少要找多少銅板
解法:
每次都將最接近的銅板納入計算後再找下一個，直到達成目標。
題目:
在銀行提款時，常常會拿到以最少紙鈔、硬幣組成的現金

要怎麼才能 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

解法

#include<iostream>
using namespace std;

int main()
{
    int money[7]={1000,500,200,100,50,10,5,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;
}

註解:
某個錢幣所需個數即是該數除以目標之商

This site is open source. Improve this page.