Hello Everyone,
Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, … , Cm} valued coins, what is the minimum number of coins to make the change? If it’s not possible to make change, print -1.
Examples:
Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents
Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents
Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, … , Cm} valued coins, what is the minimum number of coins to make the change? If it’s not possible to make change, print -1.
Examples:
Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents
Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents
Below is Dynamic Programming based solution.
// A Dynamic Programming based C++ program to find minimum of coins
// to make a given change V
#include<bits/stdc++.h>
using namespace std;
// m is size of coins array (number of different coins)
int minCoins( int coins[], int m, int V)
{
// table[i] will be storing the minimum number of coins
// required for i value. So table[V] will have result
int table[V+1];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for ( int i=1; i<=V; i++)
table[i] = INT_MAX;
// Compute minimum coins required for all
// values from 1 to V
for ( int i=1; i<=V; i++)
{
// Go through all coins smaller than i
for ( int j=0; j<m; j++)
if (coins[j] <= i)
{
int sub_res = table[i-coins[j]];
if (sub_res != INT_MAX && sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
if (table[V]==INT_MAX)
return -1;
return table[V];
}
// Driver program to test above function
int main()
{
int coins[] = {9, 6, 5, 1};
int m = sizeof (coins)/ sizeof (coins[0]);
int V = 11;
cout << "Minimum coins required is "
<< minCoins(coins, m, V);
return 0;
}
Output:
Minimum coins required is 2
Time complexity of the above solution is O(mV).