make chance - least coins algorithm

[fulyaoner]

Hi to everyone...
I am to write a code about finding the least coins number to make up an amount that is given by user.
It is a trivial question for a programmer and I did code well.
In Canada, there are 2 more currencies, Loonie = 1$ and Twonie = 2$
There is no problem to solve with the currencies.


But the tricky part, there is an extra currency that is not really is called "Jonnie = 1.31$" , that is to make the problem harder.

for example

User enters $4.63. Your output should be:
The least number of coins required to make up $4.64 is 4. The coins needed are:
1 Twonie $2.00
2 Jonnies $2.62
1 Penny $0.01
____________             
            $4.63

#include <stdio.h>
#include <stdlib.h>
#define FLUSH while (getchar() != '\n')
void makechange(int, int*);
int main(void)
{
  int  i;
  double money;
  int numsread = 0;
 
 int change[7];
  char *moneytype[7] = {"Twonie(s)\n","Jonnie(s)\n", "Loonie(s)\n", "Quarter(s)\n", "Dimes\n", 
   "Nickel(s)\n", "Penny(ies)\n"};
  while (numsread == 0) {
    printf("Please enter the amount of money you would like changed: ");  
    numsread = scanf("%lf", &money);
    FLUSH;
  }
  money *= 100;
 
  makechange(money, change);
  for (i=0; i < 7; i++) {
    printf("%d ", change[i]);
    printf(moneytype[i]);
  }
  system("pause");
  return 0;
}
void makechange(int moneytotal, int* result)
{
  int i;
 
  int moneyvalues[7] = {200, 131, 100, 25, 10, 5, 1};
 
  for (i = 0; i < 7; i++) {
    result[i] = moneytotal / moneyvalues[i];
    moneytotal -= moneyvalues[i] * result[i];
  }
 
}

Can anyone give me an idea or a way to solution to this question?
thanks

[Lazaro Claiborn]

Hi to everyone... I am to write a code about finding the least coins number to make up an amount that is given by user. It is a trivial question for a programmer and I did code well. In Canada, there are 2 more currencies, Loonie = 1$ and Twonie = 2$ There is no problem to solve with the currencies. But the tricky part, there is an extra currency that is not really is called "Jonnie = 1.31$" , that is to make the problem harder. for example[/code] Can anyone give me an idea or a way to solution to this question? thanks

You might want to take the amount entered by the user, check to see if the amount is greater than what the coins are worth and skip that coin if it is. Once you reach the coin that doesn't exceed the amount given by the user, you can start dividing the amount given by the coins value until the resulting amount is less than the that coin amount. Example;
Quarter = 25 cents
Dime = 10 cents
Nickel = 5 cents
Penny = 1 cent

Amount given = $2.20
If amount given is greater than Quarter divide until the resutling amount is less than 25 cents. Move on if and when it is.
If amount given is greater than Dime divide until resulting amount is less than 10 cents.... and so on until you get exhaust the amout given.

Of course you'd keep a counter such as a quarter, Dime and etc counter. Anyway that is one Idea.

Good luck, LamaBot

[Infarction]

To summarize the algorithm provided by Lazarus, you just add as many of the biggest coin you can. Then repeat for the next biggest until you have the amount.

[John A]

Actually the OP more-or-less did this. The algorithm does not work. Let's take what the program's output is supposed to do in this example:

User enters $4.63. Your output should be:
The least number of coins required to make up $4.64 is 4. The coins needed are:
1 Twonie $2.00
2 Jonnies $2.62
1 Penny $0.01
____________             
            $4.63

Now with your algorithm:$2.00 is largest, and it goes into $4.63 twice
Remaining change is $0.63
Since Joonies can't divide into $0.63, it's forced to go to the next one, which is the quarter
Do you see the logic? This is what the OP meant when he/she said that "Joonies make it harder". There must be a simple solution to this, but at the moment my brain is not working.

[WaltP]

The code you posted seems to work fine for me... I get

Please enter the amount of money you would like changed: 4.63
2 Twonie(s)
0 Jonnie(s)
0 Loonie(s)
2 Quarter(s)
1 Dimes
0 Nickel(s)
3 Penny(ies)

thats:
4.00  2 Twonie(s)
      0 Jonnie(s)
      0 Loonie(s)
 .50  2 Quarter(s)
 .10  1 Dimes
      0 Nickel(s)
 .03  3 Penny(ies)
-----
4.63

[fulyaoner]

The code you posted seems to work fine for me... I get

Please enter the amount of money you would like changed: 4.63
2 Twonie(s)
0 Jonnie(s)
0 Loonie(s)
2 Quarter(s)
1 Dimes
0 Nickel(s)
3 Penny(ies)
 
thats:
4.00  2 Twonie(s)
      0 Jonnie(s)
      0 Loonie(s)
 .50  2 Quarter(s)
 .10  1 Dimes
      0 Nickel(s)
 .03  3 Penny(ies)
-----
4.63

Sure the code works fine, but the output should include the jonnies, and this is the tricky part. In my solution, 8 coins is used. but the better solution must include 4 coins, which is 2 Jonnies (2.62), 1 Twonie (2.00) , 1 Penny.

thanks for all posts, but still I could not figure it.:confused:

[Infarction]

Actually, my brain wasn't really functioning either, now that I look at it. The no-brainer algorithm we all jumped on works so long as the coins are multiples of each other, or have a fairly high greatest denominator.

A more complicated algorithm would be about as follows:
1. Take the largest coin possible and subtract it. Now find the best way of creating the remainder, recursively.
2. Then take the next best option from the original amount, and recursively find it's best. If at any point, the best cannot be better than a solution already found, break. Compare this to the result for part 1 and keep the better solution.
3. Repeat 2 as feasible. In this instance, you'd only have to do it twice (once for toonies, once for jonnies), since a $2 is always better than 2x$1.

[Salem]

Seems to me like it's a variation of the knapsack problem.
http://en.wikipedia.org/wiki/Knapsack_problem

One way would be
- all permutations of 1 coin
- all permutations of 2 coins
- all permutations of 3 coins
etc

For each permutation, add them up and see if they match the total you want.

[fulyaoner]

Seems to me like it's a variation of the knapsack problem. http://en.wikipedia.org/wiki/Knapsack_problem One way would be - all permutations of 1 coin - all permutations of 2 coins - all permutations of 3 coins etc For each permutation, add them up and see if they match the total you want.

Thanks for all replies but I am not able to complete it yet.
there is a tricky part and I dont see this, :sad:

[Aia]

I'm having trouble also coming with my own solution.
It would be great if someone would post an example of:

all permutations of 2 coins

I'll keep working on it.

[Boldgamer]

Why not make it simple. I had to do something like this in the early part of a book I was learning from. Here is the code for it:

#include <iostream>
using namespace std;

int main()
{
    int total, quartars, dollars, dimes, nickels, pennies, leftover;

    cout << "Enter the total number of pennies you have: ";
    cin >> pennies;

    total = pennies;
    dollars = total/100;
    leftover = total%100;
    quartars = leftover/25;
    leftover = leftover%25;
    dimes = leftover/10;
    leftover = leftover%10;
    nickels = leftover/5;
    leftover = leftover%5;
    pennies = leftover;

    cout << "You have " << endl << endl;
    cout << "Dollars: " << dollars << endl
        << "Quartars: " << quartars << endl
        << "Dimes: " << dimes << endl
        << "Nickels: " << nickels << endl
        << "Pennies: " << pennies << endl << endl;
    return 0;
}

Could something like this be done? Or does the modulous(sp?) operator only work on integers?

[John A]

>Why not make it simple.
Why not read the entire thread so that you actually know the problem that's going on?

The OP's code worked fine for that. As stated previously, the algorithm works as long as the amounts are multiples of each other. When they're not, you have to use an optimizing algorithm to find the best method.

>does the modulous(sp?) operator only work on integers?
It works on any number type as far as I know.

[Aia]

>does the modulous(sp?) operator only work on integers? It works on any number type as far as I know.

The modulus operator can be use only with integer operands

[John A]

>The modulus operator can be use only with integer operands
Right. If it were a float there'd be no remainder.

[~s.o.s~]

A simpler way would be to convert each and everything to intger and do away with the floating point confusion and havoc.

Penny - 0.01
Scaled Penny - 1 ( scaled by factor of 100 )

And in the same way, you scale the amount entered by the user and your calculations would be made simpler.

Also if you want an equivalent of modulus operator for floats look for [search]fmod[/search] but keep in mind that it operates only with floating point numbers.

[Boldgamer]

>Why not make it simple. Why not read the entire thread so that you actually know the problem that's going on?

Sorry :sad: I missed the word "least".

[iamthwee]

I used a dynamic approach mentioned below to successfully get the correct anwer. It shouldn't take more than five minutes to code. (but then I am a member of topcoder.com he he)

http://www.student.cs.uwaterloo.ca/~cs341/Old_courses/W03/section1/Unit07.pdf

http://www.student.cs.uwaterloo.ca/~cs341/Old_courses/W03/section2/sli-dynprog.pdf

[WaltP]

You need 3 coin arrays:
A) The best coin solution so far
B) The last permutation of the coin solutions
C) The next (working) permutation being calculated.

1) First solution (A) is your initial run with 2 twonies.
2) Load that solution also into (B).

3) Load the next permutation based on (B) into (C) 
4) Load (B) with (C) for the next permutation. 
5) If (C) yields a better solution, replace (A). 
6) Generate next permutation at step #3

[Aia]

@ amthwee

Thank you for those pdf files full with information.

[fulyaoner]

and now, we have got a solution like that, if works fine for the given test values like,
User enters $4.63. Your output should be:
The least number of coins required to make up $4.64 is 4.
The coins needed are:
1 Twonie $2.00
2 Jonnies $2.62
1 Penny $0.01
$4.63

User enters $2.87. Your output should be:
The least number of coins required to make up $2.87 is 3. The coins needed are:
2 Jonnies $2.62 1 Quarter $0.25
$2.87

User enter $16.10. Your output should be:
The least number of coins required to make up $16.10 is 9.
The coins needed are:
8 Twonies $16.00
1 Dime $ 0.10
$16.10

----
but when i test the value 8.10, it gives the worst solution.
thanks