Difficult Coin exchange algorithm

user_8847596 0
Viewed 150

I'm trying to build an exchange algorithm to exchange coins in the same number as they are in stock. I have a dictionary containing key-value pairs of denomination & amounts

The input is the value to return for example €2,80 I need an algorithm to calculate the best way to return the money taking the stock into account.
(The best way is the way where the numbers of coins left in stock have the lowest standard deviation, this means the stock for all denominations is the same) So in this example I need to return coins of €1, 20ct & 10ct because €2 and 50ct coins are almost out of stock. The best output in this case is:

 {200, 0}, 
 {100, 2}, 
 {50, 0}, 
 {20, 3},
 {10, 2}

How can i calculate the best numbers to return per denomination using a c++ algorithm and keep the stock the same for all coins?

#include <map>

static map<int, int, greater<int>> ValueAmount = {
    {200, 3}, 
    {100, 20}, 
    {50, 2}, 
    {20, 15},
    {10, 14}
};

std::map<int, int> PayoutAlgorithm(std::map<int, int> ValueAmount, long amountToPay){
    
}

int main(int argc, char** argv){
    ...

    bool succes = ReturnMoney(PayoutAlgorithm());

    ...
    return 1;
}

where map ValueAmount is a key-value pair. Key is denomination of coin, value is amount of coins present.

math algorithm c++
1 Answers

The way to solve a problem like this is to break it down into something more understandable.

  1. Are we happy with our data structure? Frankly, I'd use a class that held the amount and the count, not two different arrays, but that's me.

  2. Determine how much do I need to give them (in your lowest value -- NO FLOATING POINT). 127 cents, for instance.

  3. Start handing out coins, starting with the biggest denomination and moving down. For instance, a 1-pound coin, a 25-cent coin, and 2 1-cent coins.

  4. If you run out of a particular coin, then you have to just use more of the next lower denomination.

user_13619010
Related