coin change problem(동전교환문제)

A simple example illustrates the greedy approach. Joe, the sales clerk, often encounters the problem of giving change for a purchase. Customers usually don’t want to receive a lot of coins. For example, most customers would be aggravated if he gave them 87 pennies when the change was $0.87. Therefore, his goal is not only to give the correct change, but to do so with as few coins as possible.

정확하게 거스름돈을 건네주면서 가능한 코인을 적게 주는 것이 이 문제의 핵심이다.

보통의 고객은 잔돈으로 많은 동전을 받기를 꺼려한다는 점을 상기하자. 잔돈을 거슬러주거나 받을 때 우리는 무의식적으로 탐욕적인 방법을 이미 사용하고 있다.

Example A greedy algorithm for giving change. The amount owed is 36 cents.

위의 그림은 주어진 문제에 대하여 탐욕적인 접근 방법을 잘 보여주고 있다. 36센트를 맞춰야 하므로 먼저 가장 큰 25센트를, 그 다음엔 10센트를, 마지막으로 1센트를 잡음으로써 최적의 해답에 도달한다. (￠36 = ￠25 ＋ ￠10 ＋ ￠1)

Example The greedy algorithm is not optimal if a 12-cent coin is included. The amount owed is 16 cents.

12센트짜리가 포함된 상태로 16센트를 거슬러줘야 한다. 탐욕 알고리즘으로 얻어진 해답은 (￠16 = ￠12 ＋ ￠1 ＋ ￠1 ＋ ￠1 ＋ ￠1) 로 동전의 개수가 5개이다. 하지만 최적의 해답은 (￠16 = ￠10 ＋ ￠5 ＋ ￠1) 으로 동전의 개수가 3개 임을 알 수 있다.

결론적으로 탐욕 알고리즘은 항상 최적의 해를 보장하지 못한다. 따라서 알고리즘으로 부터 얻은 결과가 최적의 해답인지를 반드시 검증해야 한다.

Change Problem Algorithm

Pseudocode

while (there are more coins and the instance is not solved)
{
    Grab the largest remaining coin; // selection procedure

    // feasibility check
    if (adding the coin makes the change exceed the amount owed)
        reject the coin;                
    else
        add the coin to the change;
    // solution check
    if (the total value of the change equals the amount owed)
        the instance is solved;
}