# Ticket automat

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:

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

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