You want to drive from A to B, and you promised to you would stop for coffee oft

Question

You want to drive from A to B, and you promised to you would stop for coffee often – no more than 100 miles between coffee stops. You want to stop for coffee as few times as possible. You are given a route, and an unsorted list of every coffee joint on that route. For each coffee joint you know how many miles it is from A on your route. Come up with the following greedy algorithm to choose your stops: start with a coffee in A; whenever you get coffee you choose the furthest coffee joint that is within 100 miles on your route, that is, the last coffee joint you reach before you hit the 100 mile limit. Drive to that joint, and get some coffee. Keep doing this until you buy coffee within 100 miles of B, at which point you can safely drive into B. (a) Prove that this algorithm produces an optimal schedule, that is, there is no schedule satisfying your 100-mile promise that has fewer coffee stops on your route.

Explanation / Answer

Greedy Introduction:
Greedy algorithms are simple and straightforward. They are shortsighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Many problems cannot be solved correctly by greedy approach. Greedy algorithms are used to solve optimization problems

Greedy Approach

Greedy Algorithm works by making the decision that seems most promising at any moment; it never reconsiders this decision, whatever situation may arise later.

As an example consider the problem of "Making Change".

Coins available are:

dollars (100 cents)
quarters (25 cents)
dimes (10 cents)
nickels (5 cents)
pennies (1 cent)

Problem Make a change of a given amount using the smallest possible number of coins.

Informal Algorithm

Start with nothing.
at every stage without passing the given amount.
add the largest to the coins already chosen.

Formal Algorithm

Make change for n units using the least possible number of coins.

MAKE-CHANGE (n)
C {100, 25, 10, 5, 1} // constant.
Sol {}; // set that will hold the solution set.
Sum 0 sum of item in solution set
WHILE sum not = n
x = largest item in set C such that sum + x n
IF no such item THEN
RETURN "No Solution"
S S {value of x}
sum sum + x
RETURN S

Example Make a change for 2.89 (289 cents) here n = 2.89 and the solution contains 2 dollars, 3 quarters, 1 dime and 4 pennies. The algorithm is greedy because at every stage it chooses the largest coin without worrying about the consequences. Moreover, it never changes its mind in the sense that once a coin has been included in the solution set, it remains there.

Characteristics and Features of Problems solved by Greedy Algorithms

To construct the solution in an optimal way. Algorithm maintains two sets. One contains chosen items and the other contains rejected items.

The greedy algorithm consists of four (4) function.

A function that checks whether chosen set of items provide a solution.
A function that checks the feasibility of a set.
The selection function tells which of the candidates is the most promising.
An objective function, which does not appear explicitly, gives the value of a solution.

Structure Greedy Algorithm

Initially the set of chosen items is empty i.e., solution set.
At each step
item will be added in a solution set by using selection function.
IF the set would no longer be feasible
reject items under consideration (and is never consider again).
ELSE IF set is still feasible THEN
add the current item.

Definitions of feasibility

A feasible set (of candidates) is promising if it can be extended to produce not merely a solution, but an optimal solution to the problem. In particular, the empty set is always promising why? (because an optimal solution always exists)

Unlike Dynamic Programming, which solves the subproblems bottom-up, a greedy strategy usually progresses in a top-down fashion, making one greedy choice after another, reducing each problem to a smaller one.

Greedy-Choice Property

The "greedy-choice property" and "optimal substructure" are two ingredients in the problem that lend to a greedy strategy.

Greedy-Choice Property

It says that a globally optimal solution can be arrived at by making a locally optimal choice.

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):

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.
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

/**
This programs uses the greedy algorithm to give the least
amount of change back.
*/

# 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)? ");
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 != ' ');
  
}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 Number of coins used= %d ", numQ, numD, numN, numP, count);

system("pause"); //Comment this out if you are not using windows operating system
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.