ContextIf you have to pay an amount of money at a store and have a limited collection of payment items (i.e. coins and banknotes) -- let's for simplicity assume there are only coins -- a trivial algorithm is to always greedily pick the biggest coin that is smaller or equal to the remaining value you have to pay. Another is to first pick the next bigger coin, before trying smaller ones. Since you are allowed to pay more than required (and will receive change by the cashier) these algorithms always works, if you have enough money.Problem formulationHowever, I pay differently (see below), and while trying to formalise (and perhaps improve) the algorithm that my brain does all by itself, I found that I had trouble to come up with a sound formal definition of the problem, not an algorithm to solve it.ProcedureI always try to get rid of as many coins as possible, while assuming the cashier is always forced to return the smallest possible number of coins (supported by the respective currency) to express the change, and has infinitely many coins of each available value.ExampleFor example, assume we have a currency with $1\cdot 10^k, 2 \cdot 10^k, 5 \cdot 10^k$ coins for all natural $k$ including $0$ (e.g. Euro-cent, considering a $1$ Euro coin as a $100$ cent coin, and a 10 Euro note as a 1000 cent coin). Assume we have to pay $61$, and have the coins $(1,20,20,100)$. The greedy algorithm, would simply pay the $100$ coin and end up with $(1,2,2,5,10,20,20,20)$, while I would pay $(1,20,100)$ and end up with $(10,20,50)$, which looks much better in my wallet.ApproachMy first attempt to define the criteria for a good algorithm was this: Minimise the total number of coins you end up after paying. However, this doesn't work, because the optimal algorithm would be to simply hand over all money in your wallet to the cashier and have them minimise the number of coins (by definition they are forced, and in reality, they usually do). This is obviously not something that would be considered a good payment algorithm in reality. If I buy some bread at a bakery and empty my entire wallet (paying more by orders of magnitude), the clerk would have all legitimation to give me funny looks.Let's try againI thought I could fix this by using a minimal set of coins that would satisfy the required sum of money, i.e. if you remove any single coin, you end up with less money than you have to pay.This clearly doesn't work, because I want to use small coins (e.g. $1$) like in the example above to prevent the cashier from splitting up quantities that can almost be paid with a single coin (e.g. $50$) with a whole bunch of coins (e.g. $(2,2,5,20,20)$).My last attempt was to say, the largest coin in the collection of payment is required to contribute the required sum. So, if I have to pay $10$, it would be admissible (though, useless) to pay with the coins $(5,10)$ but not the coins $(5,5,10)$.I don't think this works, because I should be able to pay $1$ with $(2,2,2)$ in order to get a $5$ back (but I'm not sure if all cashiers would support such a thing).QuestionWhat would be a formal definition for evaluating the performance of a given paying algorithm, according to the previous informal characterisation?NoteI would refrain from including constraints such as you shouldn't try to buy a car with pennies as an algorithm that exhibits such behaviour is irrelevant in practice (more precisely, no algorithm will get the chance to exhibit that behaviour in practice). It cannot be formalised at which amount the payment becomes ridiculous, as it depends on the cashier's mood at which point they will reject small change. Also, the amount a cashier will allow you to overshoot is subjective. As I said, I would consider it okay to pay a 1 article with three 2 coins (thus, overshooting by factor five). Some cashiers will understand and hand me a 5 note back and some will not and return me my two 2 coins and one 1 coin with a puzzled face.If you start to take such things into account, you will have to take into account whether there is a queue behind you, or how well you will perform in the future (with possibly larger queues) if you take some time now to get rid of small coins. You will need a statistical model for queue lengths at given stores and an estimate of how long your algorithm will take to find the optimal and to find a close-to-optimal solution. You see, it gets overly complicated quite easily.
How to formalise efficient payment with a collection of coins in a wallet?
combinatorics