Greedy Algorithm to find Minimum number of Coins

Given a value V, if we want to make change for V Rs, and we have infinite supply of each of the denominations in Indian currency, i.e., we have infinite supply of { 1, 2, 5, 10, 20, 50, 100, 500, 1000} valued coins/notes, what is the minimum number of coins and/or notes needed to make the change?

Examples:

Input: V = 70
Output: 2
We need a 50 Rs note and a 20 Rs note.

Input: V = 121
Output: 3
We need a 100 Rs note, a 20 Rs note and a 
1 Rs coin.

[ad type=”banner”]

The idea is simple Greedy Algorithm. Start from largest possible denomination and keep adding denominations while remaining value is greater than 0. Below is complete algorithm.

1) Initialize result as empty.
2) find the largest denomination that is 
   smaller than V.
3) Add found denomination to result. Subtract 
   value of found denomination from V.
4) If V becomes 0, then print result.  
   Else repeat steps 2 and 3 for new value of V

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20find%20minimum%20number%20of%20denominations%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20All%20denominations%20of%20Indian%20Currency%0Aint%20deno%5B%5D%20%3D%20%7B1%2C%202%2C%205%2C%2010%2C%2020%2C%2050%2C%20100%2C%20500%2C%201000%7D%3B%0Aint%20n%20%3D%20sizeof(deno)%2Fsizeof(deno%5B0%5D)%3B%0A%20%0A%2F%2F%20Driver%20program%0Avoid%20findMin(int%20V)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20result%0A%20%20%20%20vector%3Cint%3E%20ans%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20through%20all%20denomination%0A%20%20%20%20for%20(int%20i%3Dn-1%3B%20i%3E%3D0%3B%20i–)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20denominations%0A%20%20%20%20%20%20%20%20while%20(V%20%3E%3D%20deno%5Bi%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20V%20-%3D%20deno%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20ans.push_back(deno%5Bi%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20result%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20ans.size()%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20ans%5Bi%5D%20%3C%3C%20%22%20%20%22%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%0Aint%20main()%0A%7B%0A%20%20%20int%20n%20%3D%2093%3B%0A%20%20%20cout%20%3C%3C%20%22Following%20is%20minimal%20number%20of%20change%20for%20%22%20%3C%3C%20n%20%3C%3C%20%22%20is%20%22%3B%0A%20%20%20findMin(n)%3B%0A%20%20%20return%200%3B%0A%7D%0A” message=”c” highlight=”” provider=”manual”/]

output:

Following is minimal number of change for 93 is 50  20  20  2  1

Note that above approach may not work for all denominations. For example, it doesn’t work for denominations {9, 6, 5, 1} and V = 11. The above approach would print 9, 1 and 1. But we can use 2 denominations 5 and 6.
For general input, we use below dynamic programming approach.

[ad type=”banner”]