Using the best combination of notes & coins to pay for my goods

I’m a few months into using of Adalo (I’m currently using the free version) and I’ve put together an App with some Collections, Screens, a NumPad, Lists, Forms & Links.

What I’m trying to achieve an App to help people who have limited numeracy and money skills to use the best combination of the notes & coins that they have in their pocket to pay for their purchase. The App is building out OK however I’m stuck on how to calculate the best combination of the notes & coins, which is the core of the App.

I’ve tried some AI and it gets me “so far” in trying to create a function or method for “calculateBestDenominations”. Any thoughts on how to make this work would be greatly appreciated.

Hi @JimmyG,

Long story short: in Adalo this will be long and painful.

Now some explanation.

To start with: how are you going to define the “best combination” formally? Is is a minimum number of coins/notes? Or there is some criteria for remaining coins/notes? Or anything else?

If we’re talking about the minimum number of coins, this is called a “Change Making Problem” or “Coin Change Problem” (Change-making problem - Wikipedia).
For the “canonical” coin systems it can be solved with a Greedy Algorithm: you iteratively take the maximum denomination(s) possible for the remaining amount. Please see here: combinatorics - When can a greedy algorithm solve the coin change problem? - Computer Science Stack Exchange.

In your example:
23.45 → take 20, 3.45 left
3.45 → can’t take 10, 5, can take 2, 1.45 left
1.45 → take 1, 0.45 left
0.45 → can’t take 0.50, take 0.20 two times, 0.05 left
0.05 → take 0.05.
So the result is: 120 + 12 + 11 + 20.20 + 1*0.05.

In most of the modern world’s coin systems, greedy algorithm should work, but that’s not always the case. For common case this problem can be solved with dynamic programming. If you search with the keywords “minimum number of coins dynamic programming” or “greedy algorithm to find minimum number of coins”, you can find some interesting results.

In Adalo you may try to approach this problem by creating a series of formulas - for each denomination - take the integer part of the division as a result to display number of notes/coins, and somehow use the remainder of the division as a “base” for the next division. E.g. if the maximum note is 20:

  • for number of 20s the formula will be INT (amount/20) = INT (23.45/20) = 1
  • for number of 10s the formula will be INT ( ( (amount) - INT (amount/20) * 20 ) / 10 ) = INT ((( 23.45 - INT (23.45/20)*20 / 10 ) = INT ( 3.45 / 10 ) = 0
    an so on and so forth. Last formulas will be really huge (although maybe they could be optimized).
    Also if you’d like to add an existing number of coins/notes to these formulas, this will add more complexity.

So I would advise doing it with a regular programming function.

Best,
Victor.

P.S. ChatGPT provides pretty decent result when asked to create such function - the code seems to be working. You need to use correct prompt though :slight_smile:

G’day Victor, Fantastic information, thank you. I’ve done some reading on the Greedy Algorithm over the weekend and I “kind of” understand it. My thinking is for the user (or someone who supports them) to first set up their App “bank” to reflect what they physically have in their wallet or purse. Then the user to be able to type in the total amount of the item they are purchasing, click a button, and then for the App to display the best combination of the available notes & coins that the user physically has in their wallet/purse. I’ll continue to search and read about "minimum number of coins dynamic programming” and “greedy algorithm to find minimum number of coins”, do my best to understand it, and try some things. Great steps in the right direction. Thanks, JimmyG.

1 Like

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.