Given a set of denominations and an amount, how do we minimize the number of coins to make up the given amount?
Let us consider the set of denominations {1,3,4}. Also assume that we have infinite supply of coins for each denomination. To make change for 6, we can have three combinations
{1,1,4}
{1,1,1,3}
{3,3}
The minimum number of coins to make change for 6 is ‘2‘.
This problem can be efficiently solved using dynamic programming approach. Let us formulate the problem in terms of it’s sub-problems.
Let the amount be T and the given denominations are {d1,d2,…dn}. Create an array of size (T+1) denoted by MC[].
MC[K] denotes the minimum number coins required for amount K. It can be defined as follows
Min{ MC[K-d1], MC[K-d2],…MC[K-dn] } + 1
This means that we can find the solution of a problem from it’s sub-problems and it has optimal sub-structure property suggesting the dynamic programming solution.
Following is the C++ implementation of the above algorithm.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| #include <climits> | |
| using namespace std; | |
| int getMinCoins(vector<int> & denom, int amount) | |
| { | |
| int * counts = new int[ amount + 1 ]; | |
| int coins = 0; | |
| counts[0] = 0; | |
| int i, j; | |
| for( i = 1; i <= amount; i++ ) | |
| { | |
| coins = INT_MAX; | |
| for( j = 0; j < denom.size(); j++ ) | |
| { | |
| if( denom[j] <= i )//coin value should not exceed the amount itself | |
| { | |
| coins = min( coins, counts[i-denom[j]] ); | |
| } | |
| } | |
| if( coins < INT_MAX ) | |
| counts[i] = coins + 1; | |
| else | |
| counts[i] = INT_MAX; | |
| } | |
| coins = counts[amount]; | |
| delete[] counts; | |
| return coins; | |
| } | |
| int main() | |
| { | |
| int n, amount; | |
| cin >> n >> amount; | |
| vector<int> denom(n); | |
| int i; | |
| for( i = 0; i < n ; i++ ) | |
| { | |
| cin >> denom[i]; | |
| } | |
| cout << "Minimum number of coins: " << getMinCoins(denom, amount) << endl; | |
| return 0; | |
| } |
by