© Parineeth M R
Question 55. Given a set of coin denominations, find the change for a given amount using the least number of coins. For instance, suppose the coin denominations are 4¢, 5¢ and 7¢, then to get 13¢ using the least number of coins, we need to pick two 4¢ coins and one 5¢ coin.
Let us say that coin denominations are 1¢, 5¢ and 25¢. We can use a greedy approach as follows – Pick the maximum number of coins with the highest denomination and then the maximum number of coins with the next highest denomination and so on. So if we have to pick the change for 58¢, we pick two 25¢, then one 5¢ and finally three 1¢. So we use a total of 6 coins. Greedy approach produces the optimal result for this set of coin denominations. However, given any arbitrary set of coin denominations, the greedy approach will fail for many cases. For instance let the denominations be 1¢, 3¢, 4¢ and 5¢. If we use the greedy approach to get 7¢, we use one 5¢ and two 1¢ thereby requiring three coins. However the optimal solution needs only two coins (one 3¢ and one 4¢).
To solve the problem for any possible coin denominations, we use dynamic programming. We first solve the minimum number of coins needed for the amount of 1¢, then for the amount of 2¢ and so on till we reach the required amount. To compute the minimum number of coins for a higher amount, we make use of the already computed minimum number of coins for lower amounts. The formula used is
If amount = 0, minNumCoins(0) = 0
If amount > 0, minNumCoins(amount) = minimum of { 1 + minNumCoins(amount – denomination)} for all denominations which are less than or equal to the amount
For instance, let the denominations be 1¢, 3¢, 4¢ and 5¢. Using the formula above, minNumCoins[0¢] = 0 coins. The table below shows how the calculation is done for minNumCoins for 1¢, 2¢ and 3¢
So minNumCoins(1¢) = 1, minNumCoins(2¢) = 2 and minNumCoins(3¢) = 1. Similarly we find that minNumCoins(4¢) = 1 and minNumCoins(5¢) = 1. The calculations for 6¢ and 7¢ are shown below
So the minimum number of coins for 7¢ is 2 coins. If the final amount is m and there are n denominations, the time complexity of this approach is O(mn).
C/C++
/*
denom: array having the coin denominations. Should have atleast 1 element
num_denom: number of denominations
final_amount: amount for which change has to be obtained
Return value: Minimum number of coins needed to represent final_amount
*/
int find_min_coins(int denom[], int num_denom, int final_amount)
{
/*Array for storing the minimum number of coins for an amount*/
int *min_num_coins = (int*) malloc( (final_amount+1) * sizeof(int));
/*Array for storing the coin denomination chosen for an amount*/
int *chosen_denom = (int*) malloc( (final_amount+1) * sizeof(int));
int i, cur_amt, smaller_amt, result;
min_num_coins[0] = 0;
for (cur_amt = 1; cur_amt <= final_amount; cur_amt++) {
min_num_coins[cur_amt] = MAX_INT_VALUE;
for (i = 0; i < num_denom; ++i) {
if (denom[i] <= cur_amt) {
smaller_amt = cur_amt - denom[i];
if (1 + min_num_coins[smaller_amt] <
min_num_coins[cur_amt]) {
min_num_coins[cur_amt] =
1 + min_num_coins[smaller_amt];
chosen_denom[cur_amt] = denom[i];
}
}
}
}
result = min_num_coins[final_amount];
printf("Minimum number of coins = %d\n", result);
/*print the chosen denominations to get the final amount*/
cur_amt = final_amount;
while (cur_amt > 0) {
printf("%d ", chosen_denom[cur_amt]);
cur_amt = cur_amt - chosen_denom[cur_amt];
}
printf(" = %d\n", final_amount);
free(min_num_coins);
free(chosen_denom);
return result;
}
Java
/*denom: array having the coin denominations. Should have atleast 1 element
finalAmount: amount for which change has to be obtained
Return value: Minimum number of coins needed to represent finalAmount
*/
public static int findMinCoins(int[] denom, int finalAmount) {
/*Array for storing the minimum number of coins for an amount*/
int[] minNumCoins = new int[finalAmount + 1];
/*Array for storing the coin denomination chosen for an amount*/
int[] chosenDenom = new int[finalAmount + 1];
minNumCoins[0] = 0;
int curAmount;
for (curAmount = 1; curAmount <= finalAmount; curAmount++) {
minNumCoins[curAmount] = MAX_INT_VALUE;
for (int curDenom : denom) {
if (curDenom <= curAmount) {
int smallerAmt = curAmount - curDenom;
if (1 + minNumCoins[smallerAmt] <
minNumCoins[curAmount]) {
minNumCoins[curAmount] =
1 + minNumCoins[smallerAmt];
chosenDenom[curAmount] = curDenom;
}
}
}
}
int result = minNumCoins[finalAmount];
System.out.println("Minimum number of coins = " + result);
/*print the chosen denominations to get the final amount*/
curAmount = finalAmount;
while (curAmount > 0) {
System.out.print(chosenDenom[curAmount] + " ");
curAmount = curAmount - chosenDenom[curAmount];
}
System.out.println(" = " + finalAmount);
return result;
}
Python
#denom: list having the coin denominations. Should have at least 1 element
#final_amount: amount for which change has to be obtained
#Return value: Minimum number of coins needed to represent final_amount
def find_min_coins(denom, final_amount) :
#List for storing the minimum number of coins for an amount
min_num_coins = [0] * (final_amount + 1)
#List for storing the coin denomination chosen for an amount
chosen_denom = [0] * (final_amount + 1)
min_num_coins[0] = 0
for cur_amt in range(1, final_amount+1):
min_num_coins[cur_amt] = MAX_INT_VALUE
for cur_denom in denom:
if (cur_denom <= cur_amt) :
smaller_amt = cur_amt - cur_denom
if (1 + min_num_coins[smaller_amt] <
min_num_coins[cur_amt]) :
min_num_coins[cur_amt] = (1 +
min_num_coins[smaller_amt])
chosen_denom[cur_amt] = cur_denom
result = min_num_coins[final_amount]
print('Minimum number of coins = {}'.format(result) )
#print the chosen denominations to get the amount
cur_amt = final_amount
while (cur_amt > 0) :
print('{} '.format(chosen_denom[cur_amt]) , end='')
cur_amt = cur_amt - chosen_denom[cur_amt]
print(' = {}'.format(final_amount) )
return result