Greedy algorythm

[PBJ]

ok i have a project where we have an amount of 2 dollars and 19 cents. we are trying to use dollars quarters nickles dimes and pennies and we have to find the minimum number of all to give back change. does any one have an idea were to start or how i would go about doing this?

[Ganon11]

Starting at the largest denomination, find out how many will fit into that, then subtract that amount and start over with the next smallest denomination. It's what people do in real life, too.

[JosAH]

Starting at the largest denomination, find out how many will fit into that, then subtract that amount and start over with the next smallest denomination. It's what people do in real life, too.

Note though that that method doesn't always yield the minimum number of coins;
imagine a silly country where they have denominations of 1, 10, 35 and 50.
The greedy approach for an amount of 70 yields three coins: 50, 10 and 10,
while the minimum number of coins would be 2: 35+35.

kind regards,

Jos

ps. lesson learned: greedy algorithms don't always result in an optimal solution ;-)

[PBJ]

so what would be a better approach

[JosAH]

so what would be a better approach

It depends on what you want to achieve; for denominations 1, 2.5, 5 the greedy
approach results in a minimum number of coins (it was designed that way ;-)
same as the 1, 2, 5 sequence, but if you want to solve that problem for any
ratio (as the silly one I sketched above) you'd better change your algorithm to
a dynamic programming approach.

kind regards,

Jos

[Ganon11]

The greedy algorithm I described above works for any currency set c where, for any coin/bill n in c, 2c(n) <= c(n+1). That is, it works for a currency set like our own where 2 pennies are smaller than or equal to a nickel, two nickels are smaller than or equal to a dime, two dimes are smaller than or equal to a quarter, etc...

When you have silly currency sets where 2c(n) is not always less than or equal to 2c(n+1), you need a better algorithm.

Back in the day, I designed an algorithm to solve this (without any knowledge of dynamic programming), but the efficiency was awful.

[kreagan]

The greedy algorithm I described above works for any currency set c where, for any coin/bill n in c, 2c(n) <= c(n+1). That is, it works for a currency set like our own where 2 pennies are smaller than or equal to a nickel, two nickels are smaller than or equal to a dime, two dimes are smaller than or equal to a quarter, etc...

When you have silly currency sets where 2c(n) is not always less than or equal to 2c(n+1), you need a better algorithm.

Back in the day, I designed an algorithm to solve this (without any knowledge of dynamic programming), but the efficiency was awful.

Now because we gave the problem away, I think he should PROVE why the above works.

//Hands paper and pen.
///Start Clock

[Nepomuk]

Now because we gave the problem away, I think he should PROVE why the above works.

//Hands paper and pen.
///Start Clock

Phew, you're clock's still running? ;-)