What is the minimum number of coins to make the change?

Software Development
#1

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).