algorithm Applications of Greedy technique Ticket automat

Example

First simple Example:

You have a ticket automat which gives exchange in coins with values 1, 2, 5, 10 and 20. The dispension of the exchange can be seen as a series of coin drops until the right value is dispensed. We say a dispension is optimal when its coin count is minimal for its value.

Let M in [1,50] be the price for the ticket T and P in [1,50] the money somebody paid for T, with P >= M. Let D=P-M. We define the benefit of a step as the difference between D and D-c with c the coin the automat dispense in this step.

The Greedy Technique for the exchange is the following pseudo algorithmic approach:

Step 1: while D > 20 dispense a 20 coin and set D = D - 20
Step 2: while D > 10 dispense a 10 coin and set D = D - 10
Step 3: while D > 5 dispense a 5 coin and set D = D - 5
Step 4: while D > 2 dispense a 2 coin and set D = D - 2
Step 5: while D > 1 dispense a 1 coin and set D = D - 1

Afterwards the sum of all coins clearly equals D. Its a greedy algorithm because after each step and after each repitition of a step the benefit is maximized. We cannot dispense another coin with a higher benefit.

Now the ticket automat as program (in C++):

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// read some coin values, sort them descending,
// purge copies and guaratee the 1 coin is in it
std::vector<unsigned int> readInCoinValues();

int main()
{
    std::vector<unsigned int> coinValues;   // Array of coin values ascending    
    int ticketPrice;                        // M in example
    int paidMoney;                          // P in example

    // generate coin values
    coinValues = readInCoinValues();
    
    cout << "ticket price: ";
    cin >> ticketPrice;
    
    cout << "money paid: ";
    cin >> paidMoney;
    
    if(paidMoney <= ticketPrice)
    {
        cout << "No exchange money" << endl;
        return 1;
    }
    
    int diffValue = paidMoney - ticketPrice;
    
    // Here starts greedy

    // we save how many coins we have to give out
    std::vector<unsigned int> coinCount;
    
    for(auto coinValue  = coinValues.begin();
             coinValue != coinValues.end(); ++coinValue)
    {
        int countCoins = 0;
        
        while (diffValue >= *coinValue)
        {
            diffValue -= *coinValue;
            countCoins++;
        }
        
        coinCount.push_back(countCoins);
    }
    
    // print out result
    cout << "the difference " << paidMoney - ticketPrice 
         << " is paid with: " << endl;
    
    for(unsigned int i=0; i < coinValues.size(); ++i)
    {
        if(coinCount[i] > 0)
            cout << coinCount[i] << " coins with value " 
                 << coinValues[i] << endl;
    }
    
    return 0;
}

std::vector<unsigned int> readInCoinValues()
{
    // coin values
    std::vector<unsigned int> coinValues;
    
    // make sure 1 is in vectore
    coinValues.push_back(1);

    // read in coin values (attention: error handling is omitted)
    while(true)
    {
        int coinValue;
        
        cout << "Coin value (<1 to stop): ";
        cin >> coinValue;
        
        if(coinValue > 0)
            coinValues.push_back(coinValue);
        
        else
            break;
    }
    
    // sort values
    sort(coinValues.begin(), coinValues.end(), std::greater<int>());
    
    // erase copies of same value
    auto last = std::unique(coinValues.begin(), coinValues.end());
    coinValues.erase(last, coinValues.end());
    
    // print array
    cout << "Coin values: ";
    
    for(auto i : coinValues)
        cout << i << " ";
    
    cout << endl;
    
    return coinValues;
}

Be aware there is now input checking to keep the example simple. One example output:

Coin value (<1 to stop): 2
Coin value (<1 to stop): 4
Coin value (<1 to stop): 7
Coin value (<1 to stop): 9
Coin value (<1 to stop): 14
Coin value (<1 to stop): 4
Coin value (<1 to stop): 0
Coin values: 14 9 7 4 2 1 
ticket price: 34
money paid: 67
the difference 33 is paid with: 
2 coins with value 14
1 coins with value 4
1 coins with value 1

As long as 1 is in the coin values we now, that the algorithm will terminate, because:

• D strictly decreases with every step
• D is never >0 and smaller than than the smallest coin 1 at the same time

But the algorithm has two pitfalls:

1. Let C be the biggest coin value. The runtime is only polynomial as long as D/C is polynomial, because the representation of D uses only log D bits and the runtime is at least linear in D/C.
2. In every step our algorithm chooses the local optimum. But this is not sufficient to say that the algorithm finds the global optimal solution (see more informations here or in the Book of Korte and Vygen).

A simple counter example: the coins are 1,3,4 and D=6. The optimal solution is clearly two coins of value 3 but greedy chooses 4 in the first step so it has to choose 1 in step two and three. So it gives no optimal soution. A possible optimal Algorithm for this example is based on dynamic programming.