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<j<k$. 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.

  • $\begingroup$ 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. $\endgroup$
    – md5
    Oct 6, 2019 at 20:35
  • $\begingroup$ 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. $\endgroup$
    – rranjik
    Oct 6, 2019 at 22:05
  • 1
    $\begingroup$ 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 $\endgroup$
    – md5
    Oct 7, 2019 at 0:15
  • $\begingroup$ @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) ? $\endgroup$
    – rranjik
    Oct 7, 2019 at 0:32
  • $\begingroup$ @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. $\endgroup$
    – rranjik
    Oct 7, 2019 at 1:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.