Greedy Coin Change
Suppose the denominations are 1, 5, 10, 25 and 100, and a shop has unlimited coins of each denomination. How can it return change using the fewest coins?
Example
Input: 36
Output: 3
Explanation: [25, 10, 1]
To reduce the number of coins, use as many large coins as possible: give priority to the largest usable denomination.
Coin change: take the largest usable coin
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
#include <stdio.h>
#include <stdlib.h>
static int cmp(const void *p1, const void *p2) {
int *num1 = (int *)p1;
int *num2 = (int *)p2;
return (*num1 > *num2) - (*num1 < *num2);
}
int get_min_coins(int *coins, int n, int price, int *solution) {
qsort(coins, n, sizeof(int), cmp);
int min_coins = 0;
for (int i = n - 1; i >= 0; i--) {
while (price >= coins[i]) {
solution[min_coins] = coins[i];
min_coins++;
price -= coins[i];
}
}
return min_coins;
}
int main(void) {
int coins[] = {1, 5, 10, 25, 100};
int n = sizeof(coins) / sizeof(coins[0]);
int price = 36;
int solution[price + 1];
int min_coins = get_min_coins(coins, n, price, solution);
for (int i = 0; i < min_coins; i++) {
printf("%d ", solution[i]);
}
printf("\n");
return 0;
}Denominations are positive integers in ascending order, with an unlimited supply. The example amount can be formed exactly. Other denomination systems require checking whether greedy remains optimal.
KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Make change one coin at a time
Make 48 using unlimited coins of 1,5,10,25. Show the remaining amount after every greedy choice and the final combination. Explain why this result cannot automatically be generalized to every denomination system.