Algorithms

Greedy Algorithm

Greedy algorithms are an approach to solving certain kinds of optimization problems. Greedy algorithms are similar to dynamic programming algorithms in that the solutions are both efficient and optimal if the problem exhibits some particular sort of substructure. A greedy algorithm builds a solution by going one step at a time through the feasible solutions, applying a heuristic to determine the best choice. A heuristic applies an insight to solving the problem, such as always choose the largest, smallest, etc.


Greedy Algorithm

In general, greedy algorithms have five components:

  1. A candidate (set, list, etc), from which a solution is created
  2. A selection function, which chooses the best candidate to be added to the solution
  3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
  4. An objective function, which assigns a value to a solution, or a partial solution, and
  5. A solution function, which will indicate when we have discovered a complete solution

Greedy algorithms produce good solutions on some mathematical problems, but not on others.

Greedy algorithms should be applied to problems exhibiting these two properties:

  • Greedy choice propertyWe can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution.

    Note:The traveling salesman problem doesn't have this property, and therefore the greedy algorithm solution isn't right for it.

  • Optimal substructureA problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems.

With a goal of reaching the largest-sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99.



Greedy Algorithms- Non Optimal Solution

randerson112358

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

Download PDF



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

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.

Greedy Algorithm Making Change

randerson112358

Problem: Given a set of coins {1,5,10,25,50} use a greedy algorithm to give the minimum amount of coins as change.

Download PDF

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
/**
   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
}





Copyright © 2013, Everything Computer Science.