up vote 2 down vote favorite

Context

If 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 formulation

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

Procedure

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

Example

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

Approach

My 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 again

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

Question

What would be a formal definition for evaluating the performance of a given paying algorithm, according to the previous informal characterisation?

Note

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

share|cite|improve this question
  • 2
    This question seems a bit problematic in that you also ask us to account for subjective social constraints. Your example with giving all your money to the cashier (which would also represent a sort of oracle-model solution to the problem of minimizing your change) is one; concern about getting more change back than the price is another; and in many jurisdictions there is both a social and even a legal entitlement to refuse large amounts of small coin (so that you cannot pay 100 by giving twenty 5 pieces). You should formalize a model of social payment constraints first, then reconsider. – Niel de Beaudrap Jul 13 '12 at 15:12
  • For what it's worth, I would caricature my own algorithm as one operating under extreme time constraints (I don't allow myself much time after learning the price to optimize the change). This has the effect, over multiple transactions, of biasing me towards ridding myself of coins of small denomination. I therefore try to round the price to a higher coin value, depending on if I have enough of the smaller coins to successfully do this. – Niel de Beaudrap Jul 13 '12 at 15:17
  • @NieldeBeaudrap: I think we can ignore some constraints (such as paying 100 by twenty 5 pieces) as any instance of the problem in the real world is likely to have only a reasonable set of available coins to begin with (i.e. I don't carry twenty 5 cent coins). So, to model this, such requirements can be neglected. But regarding the "getting more change back than the price": The formalised evaluation function should be designed to identify algorithms that do such a thing as bad. – bitmask Jul 13 '12 at 17:36
  • I suppose that what I'm asking for is for you to reformulate the question to explicitly exclude 'bad' (as in socially unacceptable) choices, even if they are practically unlikely. – Niel de Beaudrap Jul 13 '12 at 19:11
  • @NieldeBeaudrap: Well, assume I only have 5er coins (something that in our model the cashier cannot verify!), and I want to buy something for 100. If the cashier doesn't accept it, I might be unable (or refuse) to buy the merchandise. That's why I would like to actually keep the "socially unacceptable" out of the formal definition, as it is even harder to formalise. We can easily replace it with efficiency concerns: If I hand over all my cash, I have to transfer an unreasonable amount of money, which is inefficient. But there is no need to bring social constraints into it, if you ask me. – bitmask Jul 13 '12 at 20:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.