Only and all 50 coins must be utilized. I have poured over the for/while looping logic, as well as array functionality.

Can anyone give me any "hints" or straight forward logic guidance on this progject? Incidently, since this is a homework project, hinting would be preferred.

Thank you.

[This message has been edited by Rick Rodriguez (edited June 02, 2001).]

Originally posted by Rick Rodriguez:

Can anyone give me any "hints" or straight forward logic guidance on this progject? Incidently, since this is a homework project, hinting would be preferred.

It's very commendable of you to say that. I'd give you an A+ for integrity.

I suspect the modulus operator (%) would play a part in the logic and a while loop as well. You have to make some assumputions too, like what the different coin denominations are. Some countries have a 20-cent coin but no 25-cent coin.

Junilu

*Practice only makes habit, only perfect practice makes perfect.
So, practice mindfully. Practice doing the right things and doing things right. *— Junilu

[How to Ask Questions] [How to Answer Questions]

I appreciate the feedback. Have you been able to create such a program, with the parameters I have outlined?

Thanks again.

Originally posted by JUNILU LACAR:

It's very commendable of you to say that. I'd give you an A+ for integrity.

I suspect the modulus operator (%) would play a part in the logic and a while loop as well. You have to make some assumputions too, like what the different coin denominations are. Some countries have a 20-cent coin but no 25-cent coin.

Junilu

You probably need 4 nested loops, one for each coin. In the innerest(real word?) loop you would need two test conditions:

1. adding up all four loop values to see if they equal 50

2. adding up all four loop values plus mulipling by the value(.1, .5, .10., .25) to see if equals a $1.00

If they are both true, you have your answer.

Note: on the second step you would be much better off using 1,5,10,25 and seeing if it adds up 100

Also Note: If my algebra is correct, there is only one solution, if you have to use all the coins.

Sorry if this was too much or not enough.

But I hope this helps,

Bill

You said "only and all 50 coins must be used." If true, this is very simple. Add all coins up in sequence received, and if they don't make 1.00, then no other combination will do that either. If they do add up, then that must mean that ... it's on the tip of my brain...

i'll make it simpler for myself. Imagine 4 coins passed in a 4-entry array. Imagine further that they are all quarters.

The combinations are:

1,2,3,4

2,3,4,1

3,4,1,2

4,1,2,3

umm...

2,1,4,3

etc....

isn't it 4 to the 4th combinations? But maybe this logic only works because my example has been reduced to a too-simple base case.

Or for the question being asked, is this actually only one combination, and 'order' is not being considered. The problem becomes much easier if that is the case. (ie: once you find a combination of coins, you don't need to list off all possible combinations of THAT combination).

"Using any number of the 50, but only from those 50..." is probably what is meant?

You mentioned "if your algebra is correct" below. What theorem/formula did you use?

Thanks again Bill and anyone else who may be able to create this piece of code, feeding me hints afterwards.

Thanks again.

Originally posted by Bill Norton:

You only wanted hints so hear goes:

You probably need 4 nested loops, one for each coin. In the innerest(real word?) loop you would need two test conditions:

1. adding up all four loop values to see if they equal 50

2. adding up all four loop values plus mulipling by the value(.1, .5, .10., .25) to see if equals a $1.00

If they are both true, you have your answer.

Note: on the second step you would be much better off using 1,5,10,25 and seeing if it adds up 100

Also Note: If my algebra is correct, there is only one solution, if you have to use all the coins.

Sorry if this was too much or not enough.

But I hope this helps,

Bill

Have you been able to create this code? Thanks again Mike.

Originally posted by Mike Curwen:

There is a point of confusion for me:

You said "only and all 50 coins must be used." If true, this is very simple. Add all coins up in sequence received, and if they don't make 1.00, then no other combination will do that either. If they do add up, then that must mean that ... it's on the tip of my brain...

i'll make it simpler for myself. Imagine 4 coins passed in a 4-entry array. Imagine further that they are all quarters.

The combinations are:

1,2,3,4

2,3,4,1

3,4,1,2

4,1,2,3

umm...

2,1,4,3

etc....

isn't it 4 to the 4th combinations? But maybe this logic only works because my example has been reduced to a too-simple base case.

Or for the question being asked, is this actually only one combination, and 'order' is not being considered. The problem becomes much easier if that is the case. (ie: once you find a combination of coins, you don't need to list off all possible combinations of THAT combination).

"Using any number of the 50, but only from those 50..." is probably what is meant?

There is no real 'formula', but just think hard for a second. If you are given a single array of 50 coins, and you must use ALL of them to see if they add up to 1.00, then this is a TRUE/FALSE situation. Do they add up, or don't they? If they don't, then adding them up in a different order will not produce a different result. But what I get from your next comment, is that you want a list of all arrays that successfully add up to $1.00...

Your last sentence "Apparently, there are several combinations, less than 10, of 50 U.S. coins that can add up to $1.00" really helped clarify the program requirement.

The brute force method is an easy approach. You have 50 positions to fill (one for each of the 50 coins). There are four possible values in each position (1,5,10,25). That means there are 4 to the 50 combinations you must check. When you add up a certain combination, and it equals $1.00, then remember that combination. The list of combinations that adds up to $1.00 will be your answer.

This is different than what I thought you were supposed to do. I thought it was "I've given you 50 random coins. How many ways can you make $1.00? (you can use as little as 4 coins, and as many as 50)".

I am a geek with nothing better to do today.. sigh...

I think I'll work on this a bit.

p = # of pennies

n = # of nickels

d = # of dimes

q = # of quarters

You have two equations that can now be derived

p+n+d+q = 50

1p + 5n + 10d + 25q = 100 //I multiplied by 100 to make things pretty here

If you solve for p in the second equation you get

p = 100 - 5n - 10d - 25q

Now substituion p into the first equation

100-5n-10d-25q+n+d+q= 50

Simplify

-4n-9d-24q = -50

4n + 9d + 24q = 50

Now since q is the amount of quarters there are only a few possiblities. q= 1,2,3

3 would not work

So for 2-> 4n + 9d + 24(2) = 50

4n + 9d = 2

Can't work!

Therefore the only possible value left is q=1

This leaves us with a new equation

4n + 9d + 24 =50

4n + 9d = 26

Now d would have to equal 2 to make the equation

4n + 9(2) = 26

4n = 8

n=2

Any other values for 9d or 4n will not add up to 26.

Now if you don't have to use all types of coins then you could just have q=0, and get the equation

4n + 9d =50

Ther are some more possibilities there.

Well need to go lawn needs moving and it looks like rain!

Bill

ps I didn't proof read sorry for mistakes

I think the answer is:

q d n p

0 2 8 40 = 100 count = 50

1 2 2 45 = 100 count = 50

Rick, when you are done (or close), post your code and let us see how you did it.

> I have a program that finds two combinations. Anyone else?

I got the same results.

Rick, using brute force, you can find the good combinations using three "for" loops.

Junilu

*Practice only makes habit, only perfect practice makes perfect.
So, practice mindfully. Practice doing the right things and doing things right. *— Junilu

[How to Ask Questions] [How to Answer Questions]

[This message has been edited by Bob Graffagnino (edited June 04, 2001).]

>>I too got the same results using 4 "for" loops

You could probably simplify your solution. 3 nested "for" loops are sufficient really because another loop for pennies would be superfluous. Also, I didn't use any variables other than the three for-loop index variables. I did have a separate 3-line method that determined whether a combination of coins met the criteria.

Junilu

*Practice only makes habit, only perfect practice makes perfect.
So, practice mindfully. Practice doing the right things and doing things right. *— Junilu

[How to Ask Questions] [How to Answer Questions]

And then come the optimizations.

I've gone through two 'cycles' of this optimization effort, and I admit to thinking there must be a way to kill off the outer loop (the quarters loop). But now thanks to Junilu, I see now why the pennies loop was worse than useless (it's a big timewaster!). So I've got it down to three loops as well.

Hopefully Rick will tell us when the due date is, so I can see if my code is the best it could be.

1: We have w pennies, x nickels, y dimes, and z quarters.

2: w + x + y + z MUST equal 50 and there cumulative value MUST equal 100.

This allows us to conclude that only x penny values evenly divisable by 5 could complete our needs, so we can set the penny array like so... { 5, 10, 15, 20, 25, 30, 35, 40, 45 }. 0 and 50 are automatically excluded since they do not meet the minumum requirements.

Now we can write a function to whittle this down a little: we'll use 45 for the 1st example.

1: 45 pennies provides a difference of 5 coins.(50 - 45 = 5).

2: The 5 coins must total 55 (100 - 45 = 55).

*2A: Add a vlidity check here: multiply the # of coins (5) x our denominator (5) = 25. Is this less than the amount needed (55)? Yes, so you can continue. {If NOT then this number of pennies is not valid and you can stop here.}

3: Can 5 coins containing at least one nickel, one dime, and one quarter = 55? To find out we add 5 + 10 + 25 and get 40. (this could actually become a program constant)

4: 55 - 40 = 15.

5: Divide 15 by our denominator (5) = result (3).

6: A Static array of arrays could determine what the corresponding values would be (*hint: a result of 3 would point us to a positional Array[3] which would have subsequent Array[3][0]=5 and Array[3][1]=10. Array[0] and Array[1] would both be null) Deciphering the Array values will tell you which coins you need to add to your assumed coins ( 45 pennies, 1 nickel, 1 dime, 1 quarter ) to achieve a value of 100.

7: So our solution for 45 is "45 pennies, 2 nickels, 2 dimes, and 1 quarter"

Confused? Me too... let's test it with penny array 20...

1: 20 pennies provides a difference of 30 coins.(50 - 20 = 30) .

2: The 30 coins must total 80 (100 - 20 = 80).

*2A: Validity check: multiply the # of coins (30) x our denominator (5) = 150. Is this less than the amount needed (80)?

No, it is not, so this number of pennies cannot represent a valid solution.

Now that you've built the function, loop through the array and call it 9 times, printing out the good results and you should come up with

*a*correct solution. I hope this helps in some way... it may not be complete but should give you plenty to think about!

------------------

I'm a soldier in the NetScape Wars...

Joel

[This message has been edited by Joel Cochran (edited June 05, 2001).]

Wait a minute, I'm trying to think of something clever to say...<p>Joel

------------------

I'm a soldier in the NetScape Wars...

Joel

Wait a minute, I'm trying to think of something clever to say...<p>Joel

Here's a recursive solution. It prints a solution as a sequence of coins in descending order. If anyone would like to try it out you can compile it and run it at the command line to solve any problem of this form. It could easily be modified to accept coins of arbitrary denomination.

To solve the stated problem: java Coins 100 50

By the way I believe this problem is np-complete. Does anyone have any opinions on this?

Here's the basic idea of this algorithm:

The trivial case is one coin. There's a solution if the amount is equal to a valid denomination and no solution if it isn't.

Otherwise -

Remove a quarter and see if there's a solution for what you have left (amount - 25, coins - 1). Do the same with a dime, nickel, and penny.

-----------------------------------------------------------------

[This message has been edited by Tod Tryk (edited June 07, 2001).]

[This message has been edited by Tod Tryk (edited June 07, 2001).]

I appreciate your help, but we (our class) haven't learned the "Switch" statement yet. We're still on loops.

To let everyone know, tonight our teacher could not understand, after class, why I could not understand this simple concept. When he discovered that the "nested" for loop concept was not explained, either in the book or by himself last week, he reminded me to teach the rest of the class next week.

At any rate, after he explained the logic of how nested for loops work, "Eyes Are Open!"

This project is due next week for me. I will, however post my code within the next two days. Please wait to post your own until such time, as it may be deemed as "cheating" on my part, if it is inferred that I got my code from this message board.

Thank you again everyone, and come back to see my code this Saturday.

That coding example is why I back away slowly from recursion. And I haven't heard "np-complete" since I dropped out of University.

But thanks for the code, because God help me, I'm going to try and understand it.

I don't even know if it makes sense to ask if this problem is np-complete. I was wondering if there might be a way to discover all the solutions to the coin problem without exhaustive search - and then I thought - naah this problem is probably np-complete. Being very non-expert in this area I was hoping someone could shed some light on it. Anyway I think I'm getting off-topic so let me just say in conclusion - I encourage the use of logic when constructing loops that process arrays.

I started coding this program at approximately 1:00pm and finished at approximately 2:00pm, ET. Most of that time was spent in my IDE's debug session, looking at how the 'for' loops rotate to find the parameters defined.

At any rate, here is my homework code:

Incidently, the text that my "Intro to Java" course utilizes is 'JAVA: Programming From the Beginnnig', by K.N. King. I think that this is a fantastic book for beginners, and I can only speak from that perspective, since I am a beginner.

Thanks again guys for all of your input, and let me know if I can "fine tune" my code any further.

(edited by Cindy to format code)

[This message has been edited by Cindy Glass (edited June 09, 2001).]

<pre>

class FiftyToADollar

{

public static void main(String[] args)

{

// We don't need a loop for pennies because

// we can derive the penny count from the

// count of other coins we have so far

for (int q = 0; q < 4; q++)

for (int d = 0; d < 10; d++)

for (int n = 0; n < 20; n++)

if ( isGoodCombo(q, d, n) )

System.out.println(

" 25c = " + q +

" 10c = " + d +

" 5c = " + n +

" 1c = " + (50-q-d-n));

}

// chose to move evaluation to a separate method

// to keep the main loop code clear and concise

static boolean isGoodCombo(int q, int d, int n)

{

int p = 50 - q - d - n;

return ((p + q + d + n) == 50) &&

((q*25 + d*10 + n*5 + p) == 100);

}

}

</pre>

[This message has been edited by JUNILU LACAR (edited June 10, 2001).]

So, practice mindfully. Practice doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

I have three comments.

I'm assuming the empty if() statements between your for loops were used during development for debugging? Otherwise, I can't see what they'd be used for, except perhaps a 'continue' statment? As it is, they are doing nothing...

I would also suggest there is a small (negligable) optimization that can be made to the quarters loop. You can bring the exit condition down to < 3. Also, regard how others have dropped the pennies loop... pennies are worth '1' each, and we can determine how many of them there are by how many of the other coins there are.

The last thing is also a very slight optimization, but if we are talking about efficiency, then lets squeeze everything we can out of math...Your innermost if() statement is coded thus Because Java performs short-circuited ANDs, we can realize (I know, I know) a very small boost, if you place the second test first. That way, it only does 4 additions, instead of 3 multiplications and then 4 additions. Because we need both of them to be true, we should always check the 'cheapest' side first. Once it proves to be false, Java ignores the other side of the AND (short-circuited AND). Congratulations on figuring it out.

--Freddy

------------------

I have a cute bird