In this post, you will learn Greedy Change Making Program in C programming language.
The greedy approach is easy to understand and implement as well. We start with using the largest denomination coin/currency possible. Once the owed amount is less than the largest, we move to next largest coin, so on and so forth.
Example program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <stdio.h> int main () { int num_denominations, coin_list[100], use_these[100], i, owed; printf("Enter number of denominations : "); scanf("%d", &num_denominations); printf("\nEnter the denominations in descending order: "); for(i=0; i< num_denominations; i++) { scanf("%d", &coin_list[i]); // use_these[i] = 0; } printf("\nEnter the amount owed : "); scanf("%d", &owed); for(i=0; i < num_denominations; i++) { use_these[i] = owed / coin_list[i]; owed %= coin_list[i]; } printf("\nSolution: \n"); for(i=0; i < num_denominations; i++) { printf("%dx%d ", coin_list[i], use_these[i]); } } |
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
