# Making change optimally

Consider that a currency system has $$k$$ denominations $$d_0, d_1, ... d_{k-1}$$. $$d_0, d_1, ... d_{k-1}$$ are such that $$d_0 < d_1 < ... < d_{k-1}$$ and $$d_i$$ divides $$d_j$$ for all $$0<=i. Example: ₹1, ₹5, ₹10, ₹20, ₹40, ₹80. As a cashier at a cash register I need to service $$n$$ customers, buying things that are worth $$p_0, p_1, ... p_{n-1}$$, and they pay me $$c_0, c_1, ..., c_{n-1}$$ (and of course, customers pay enough money i.e, for all $$i$$ in $$0, 1, ... n-1$$, $$c_i>=p_i$$).

I start with no cash at hand (if $$|d_j|$$ denotes the number of $$d_j$$ bills/coins I have available, then $$|d_i| = 0$$ for all $$i$$ in $$0, 1, ..., k-1$$).

I have to make change for a customer, if the amount they pay is more than the price of the stuff they want to buy ($$c_i > p_i$$).

There are two cases where I fail and stop.

1. I fail at the $$m^{th}$$ customer where I cannot make change. That is, if the cash I have available at hand is lesser than the amount I'll have to pay them back (i.e, if they pay $$c_m$$ to buy something that is worth $$p_m$$ and, $$(c_m-p_m) > (\sum_{i=0}^{k-1}|d_i|*d_i)$$). For example, the first customer has to pay the exact change, else I fail at the very first step.

2. It might be the case that, I have enough cash but I just can't make change (I don't know how to write this down formally, so I'll just give an example: A person buys something for ₹5 and pays me a ₹20 bill, but I happen to have just two ₹10 bills - though I have more money than what's required, I don't have the right denominations).

Given the setup, If I want to serve the maximum number of customers, I think an optimal strategy would be to try and spend higher denominations as much as I can before I use smaller ones. For example, suppose I have three ₹5 bills and one ₹10 bills. To pay back ₹15 I will use one ₹10 bill and ₹5 bill instead of spending the three ₹5 bills at this time.

Is this the optimal strategy ? If yes, how should I prove this is optimal. If not, what is ?

Customers have to be processed one at a time (like an online algorithm), I cannot skip someone and come back to them later.

• So you're also given for each customer the multiset of bills they give to you? If so, then your problem is at least harder than the standard change-making problem (en.wikipedia.org/wiki/Change-making_problem), your greedy approach won't work unless $(d_1, \ldots, d_k)$ satisfy some conditions. – md5 Oct 6 '19 at 20:35
• Thanks for the comment. Yes I will be given that multiset. For example, if I receive ₹20 as (1*₹10 + 2*₹5) I will update my balance and the number bills I have left of those types. Can you please explain how the standard change making problem applies here ? I have seen variations of this standard change making to solve it using the minimum number of coins/bills. But my questions is about what to choose if I have multiple ways of making change for the same amount. – rranjik Oct 6 '19 at 22:05
• Ok, I slightly misunderstood the problem at first. Now it just feels like your greedy strategy is ill-defined: you took a simple example with 10 and 5, but imagine you have to give back 15 and you have 1 bill of each amount: 10, 9, 8, 7, 6. You have two ways to give back money: 9,6 and 8,7, and whether it will be optimal or not globally depends on the next queries (in one universe, you could be asked to give back 6 right after; in another, 7...). There's a bit of hand-waving here, but basically you won't find any local optimal strategy if you don't know all queries in advance – md5 Oct 7 '19 at 0:15
• @md5 Ah thank you very much. I did not think of that! However, can I do something better if I knew $d_0, d_1, ... , d_k$ are such that $d_0 < d_1 < ... < d_{k-1}$, and $d_i$ divides $d_j$ for all $0<=i<j<k$ (say for example 5, 10, 20, 40, 80) ? – rranjik Oct 7 '19 at 0:32
• @md5 If this is the case, I think this greedy approach would work, and I should prove this by contradiction. I should pick the first customer I failed to serve, and arrive at some contradiction. I think I should use the fact that I can make change for any larger denomination given that I have enough amounts of the smaller ones. Thanks again. I realise that I did not describe the question properly. – rranjik Oct 7 '19 at 1:17