Coins Problem : An example of greedy algorithm

The greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum.

Please see details of the greedy algorithm on wikipedia.

Coins problem in "Problem contest challenge book" is an example of a greedy algorithm. The point is that you use the largest amount of coin preferentially.

---

Problem:

You have coins as bellow.

• A number of 1     yen coin is C1
• A number of 5     yen coin is C5
• A number of 10   yen coin is C10
• A number of 50   yen coin is C50
• A number of 100 yen coin is C100
• A number of 500 yen coins is C500

You want to pay A yen with the minimum number of coins. How many coins do you have to pay? There is at least one solution for this. 

Constraint

0 <= C1, C5, C10, C50, C100, C500 <= 10^9

0 <= A <= 10^9 

Sample input:

A = 620
c500 = 2, c100 = 0, c50 = 3, c10 = 1, c5 = 2, c1 = 3 

Sample output:

6

My solution:

You can find my solution for this problem on my github.

https://github.com/yohei1126/pccb/blob/master/beginner/search/GreedyAlgorithm/Coins/Coins.cpp