0

Given a dollar amount convert it into euro coins and bills. You are given the dollar amount as the argument, and said that the dollar to euro rate is 1.30. You are given that euro denomations are 500 bill, 200 bill, 100 bill, 50 bill, 20 bill, 10 bill, 5 bill, 2 bill, 1 bill, 50 cents, 25 cents, 10 cents, 5 cents, 2 cents, 1 cent. Convert that dollar amount into the least amount of bills and coins. (Convert a numerical dollar amount (such as $10.00) to an equivalent amount in Euro Bills and Coins.)

Disclaimer: This is a homework problem I've been given.

I've thought about solving it using a while loop which iterates through each of the denominations and subtracts it from the value. something like:

while(amount > 0){
  if(amount - denomination[index] > 0) {
     amount -= denomination[index];
  }else{
     index++;
  }
}

But other sources are telling me that the coin change problems is solved with dynamic programming. I'm very confused.

Rahul Chowdhury
  • 641
  • 1
  • 7
  • 16
  • Are you taking a class on dynamic programming? If not, then you probably don't need to do it that way. Have you asked your instructor whether you need to solve it using dynamic programming or whether a different solution would be acceptable? – Ken White Sep 05 '19 at 01:25
  • Also, have you done any research into existing questions on the topic here, such as [javascript making change algorithm](https://stackoverflow.com/q/42883552/62576) or [Understanding change-making algorithm](https://stackoverflow.com/q/14992411/62576) – Ken White Sep 05 '19 at 01:51
  • It is simply not true that there are 25 cents coins in the Euro system. There are 20 cents instead. – Carsten Massmann Sep 05 '19 at 07:27

4 Answers4

2

For this specific denomations set change problem might be solved by greedy method, as you did.

Same is true for sets where values differ twice like 1,2,4,8..., but rules are not simple, as @Patrick87 noticed in comment. Appropriate money systems are called "canonical", but it is not easy to find whether given system is canonical: example of discussion

For arbitrary values greedy method can fail
([1,5,15,20]gives 20+5+5 for sum=30 while 15+15 is better)

That is why in general coin change problem should be solved with dynamic programming

MBo
  • 77,366
  • 5
  • 53
  • 86
  • 1
    +1 However, the criterion is much more complicated than the denominations differing by twice or more. Consider {50, 14, 1}. To get 56 the greedy algorithm gives 1x50 + 6x1 while the optimal answer is 4x14. I'm of the opinion that the greedy method works for the proposed denominations, but to prove it I'd probably check all amounts up to $1000 with a known correct solution, then argue iductively. Might as well just write the dynamic programming solution. An elegant proof eludes me here. – Patrick87 Sep 05 '19 at 03:23
  • The criteria when to choose dynamic programming or not is considering this rule. If higher denomination can be created using the lower one, you don't need a DP solution. For example `[1, 5, 15, 20]`. The greedy approach fails because you can't have a replacement of 15 with 20 value but in the case of `[1, 5, 20]` greedy approach will work as `20` value can be replaced with `5*4` and also the 1's one. – Rahul Sep 05 '19 at 06:24
1

This answer is probably not "academic" enough, but using JavScript you can boil it down to a simple application of Array.reduce() (assuming that the "greedy" approach is applicable, which it will be for the Euro currency system):

change=amnt=>(c,d,i)=>{var rest=amnt%d;
 if (rest!=amnt) {c[i]=(amnt-rest)/d; amnt=rest;}
 return c };

var rate=110.36; // Euro cents per USD
var res=document.querySelector('#result');

document.querySelector('#USD').onkeyup=ev=>{
 var cents=Math.round(ev.target.value*90.78); // amount in Euro cents
 var denom=[50000,20000,10000,5000,2000,1000,
            5000,2000,1000,500,100,50,20,10,5,2,1];
 var coins=denom.reduce(change(cents),[]);

 res.innerHTML=cents/100+' €<br>'
   +coins.map((n,i)=>n+'x'+(denom[i]>99?denom[i]/100+'€':denom[i]+'ct'))
         .filter(v=>v).join(', ');
}
USD <input type="text" value="13" id="USD">
<div id="result"></div>
Carsten Massmann
  • 26,510
  • 2
  • 22
  • 43
0

Traditionally, currency coin change problems like the one presented to you are designed to be dynamic programming questions. Here's an example where your approach will yield the wrong answer for a similar problem with a simpler premise:

Given an unlimited number of 7$ bills, 5$ bills, 4$ bills and 1$ bills, and a certain item with price of N$, find the optimal way of purchasing the item so that you use the least amount of bills possible.

Now if I set N=12 in the previous problem, you'll see that your algorithm will indeed break down the 12$ into 1 bill of 7$ and another bill of 5$. If I set N=9 however, then you'll notice that your algorithm will break down the 9$ into a bill of 7$ and two bills of 1$, when the optimal solution is one bill of 5$ and one bill of 4$.

So is your solution correct? Turns out, it is. That's simply because your bills are given in a way that your greedy solution will always work (I tested it up to 100000.00$ just to be 100% sure). I'm sure you can find resources online that can tell you the exact reason as to why your set of bill values works with a greedy algorithm, and unfortunately, I can't provide you with a satisfying explanation. Here's a discussion related to this issue

Although you can solve your solution with a greedy algorithm, the dynamic programming (DP) approach will also yield the correct answers, and luckily for you, there are plenty of resources that can teach you about DP, if that's what's confusing you, such as GeeksForGeeks. If you're having issues implementing the DP solution, the code is posted here!

Yun Ke Xiao
  • 1
0

The problem of determining optimal representation in a coin system, in general, is weakly NP-hard. Probably, for all contemporary coin systems in the World greedy algorithm works fine. Most often contemporary coin systems use so-called binary-decimal pattern 1-2-5. But your example has 25 cents which require a closer look.

But first, let's prove that 1-2-5 pattern amenable for the greedy algorithm. Observe that their LCM is 10, this means that we need to check only numbers in [1..9].

1 = 1,0,0  4 = 0,2,0  7 = 0,1,1
2 = 0,1,0  5 = 0,0,1  8 = 1,1,1
3 = 1,1,0  6 = 1,0,1  9 = 0,2,1

So, this pattern is greedy. Let's now turn our attention to the first six denominations 50, 25, 10, 5, 2, 1. Here we have the same LCM - 50. I wrote a program to check this:

#include <iostream>
#include <array>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <iterator>

bool IsOptimal(const int sum, const int numberOfCoins, std::array<int, 6>::const_iterator begin, std::array<int, 6>::const_iterator end) {
    if (sum < 0 || numberOfCoins == 0) return true;
    for (auto it = begin; it < end; ++it) {
        const int nextSum = sum - *it;
        if (nextSum == 0) return numberOfCoins == 1;
        if (!IsOptimal(nextSum, numberOfCoins - 1, it, end))
            return false;
    }
    return true;
}

int main() {
    const std::array<int, 6> kDenoms = { 1,2,5,10,25,50 };
    for (int i = 1; i < 50; ++i) {
        std::array<int, 6> change = { 0 };
        int sum = 0;
        while (sum != i) {
            auto it = std::upper_bound(kDenoms.cbegin(), kDenoms.cend(), i - sum);
            ++change[--it - kDenoms.cbegin()];
            sum += *it;
        }
        const bool isOptimal = IsOptimal(sum, std::accumulate(change.cbegin(), change.cend(), 0), kDenoms.cbegin(), kDenoms.cend());
        std::cout << std::setw(2) << i << ": ";
        std::copy(change.cbegin(), change.cend() - 1, std::ostream_iterator<int>(std::cout, ","));
        std::cout << change.back() << " " << std::boolalpha << isOptimal << std::endl;
    }
    return 0;
}

So, basically, what do we know? We know that all quantities less than 50 we can attack with the greedy algorithm to get its optimal solution.

Observe, that all denominations above 50 are divisible by 50, so they will not interfere with 50, 25, 10, 5, 2, 1. We also proved that the greedy algorithm works for pattern 1-2-5, so the whole set of denominations amenable for the greedy algorithm.

Yola
  • 18,496
  • 11
  • 65
  • 106