Greedy Algorithm Making Change

Here we will determine the minimum number of coins to give while making change using the greedy algorithm. The coins in the U.S. currency uses the set of coin values {1,5,10,25}, and the U.S. uses the greedy algorithm which is optimal to give the least amount of coins as change. It is optimal because

• Total value of pennies: < 5 cents
• Total value of pennies and nickels: < 10 cents
• Total value of non-quarters: < 25 cents

Problems with greedy algorithm (when the greedy algorithm isn't optimal):

1. Imagine a coin set of { 25-cent, 10-cent, 4-cent} coins. The greedy algorithm would not be able to make change for 41 cents, since after committing to use one 25-cent coin and one 10-cent coin it would be impossible to use 4-cent coins for the balance of 6 cents, whereas a person or a more sophisticated algorithm could make change for 41 cents with one 25-cent coin and four 4-cent coins.
2. Say we have {1,5,10,20,25} cents, what if we wanted minimum coins for 40 cents, the optimal choice will be two 20 cent coins, but the algorithm will choose coins 25,10,and 5, three coins.

Let's use the greedy algorithm to give us the least amount of coins for 36 cents. We will use the coin set {1, 5, 10, 20}.

1. 36 - 20 = 16, List Solution: 20
2. 16 - 10 = 6, List Solution: 20, 10
3. 6 - 5 = 1, List Solution: 20, 10, 5
4. 1 -1 = 0, List Solution: 20, 10, 5, 1

Making Change Example:

An example of making change with the least amount of coins:

1. Candidate set (coin values): {1, 5, 10, 20}
2. Selection function: Choose the largest coin value first "20"
3. Feasibility function: Check if largest coin value can be used for change amount,if true then remember coin value & change amount := change amount - largest coin value else check next largest value
4. Objective function: Remember the coins being used
5. Solution function: When the change amount reaches 0 we have found our solution.

Most networking algorithms uses greedy approach. Here is the list of few of them:

• Travelling Salesman Problem
• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Minimal Spanning Tree Algorithm
• Graph - Map Coloring
• Graph - Vertex Cover
• Knapsack Problem
• Job Scheduling Problem

Code: Greedy Algorithm

/**
   This programs uses the greedy algorithm to give the least 
   amount of change back. 
   Written in the C programming language
   By: (randerson112358)
*/

# include <stdio.h>


int main(void)
{
    int changeOwed;
    int check;
    char invisibleChar;
    int count = 0;
	int numQ=0, numD=0, numN=0, numP=0;
    
      /***Run this loop until the user inputs a number and it is greater than or equal to 0***/
    do{
          printf("How much change is owed (in cents)?\n");
        check = scanf("%d", &changeOwed); // returns 1 if the input is a number and returns 0 otherwise
        
        //Get's rid of any extra invisible characters if the input is a char/String
        do{
            scanf("%c",&invisibleChar);
        }while(invisibleChar != '\n');
            
    }while(check == 0 || !(changeOwed >=0 ));
    
    
    int c = changeOwed;// The variable c was only used to shorten my typing
    //Continue to do this loop until 
	while(c > 0){
	
	    //Use as many quarters needed
		while(c >= 25){
			count ++;
			numQ++;
			c = c - 25;
		}
		//Use as many dimes needed
		while(c >= 10){
			count ++;
			numD++;
			c = c - 10;
		}
		//Use as many nickels needed
		while(c >= 5){
			count ++;
			numN++;
			c = c - 5;
		}
		//Use as many pennies needed
		while(c >= 1){
			count ++;
			numP++;
		c = c - 1;
		}

	}
    
 	printf("Quarters: %d, Dimes: %d, Nickels: %d, Pennies: %d\nNumber of coins used= %d\n\n", numQ, numD, numN, numP, count);
   
    system("pause"); //Comment this out if you are not using windows operating system
}