| Welcome to The New Coffee Room. We hope you enjoy your visit. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free. Join our community! If you're already a member please log in to your account to access all of our features: |
- Pages:
- 1
- 2
| Change for a dollar | |
|---|---|
| Tweet Topic Started: Dec 7 2011, 04:17 AM (837 Views) | |
| Klaus | Dec 7 2011, 04:17 AM Post #1 |
![]()
HOLY CARP!!!
|
To get $1.00 in coins, you have many ways, such as 4 0.25$ coins, or 2 0.25$ coins and 5 0.10$ coins. How many different sets of coins are there whose sum is $1.00? How do you compute this number in the general case (arbitrary sum, arbitrary denominations of coins)? |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| apple | Dec 7 2011, 06:23 AM Post #2 |
|
one of the angels
|
why? |
| it behooves me to behold | |
![]() |
|
| Klaus | Dec 7 2011, 06:30 AM Post #3 |
![]()
HOLY CARP!!!
|
|
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Mikhailoh | Dec 7 2011, 06:32 AM Post #4 |
|
If you want trouble, find yourself a redhead
|
Klaus has made his mark.
|
|
Once in his life, every man is entitled to fall madly in love with a gorgeous redhead - Lucille Ball | |
![]() |
|
| Klaus | Dec 7 2011, 06:40 AM Post #5 |
![]()
HOLY CARP!!!
|
More seriously, there are very practical applications that require solutions to problems like this - not with coins, but similar "packing" problems. Furthermore, if you find general solutions for very similar problems, you'll get a million dollar. For instance, if you can devise a method that can quickly find out the following similar problem, then you'll be both instantly famous and a millionaire: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Klaus | Dec 7 2011, 10:38 AM Post #6 |
![]()
HOLY CARP!!!
|
5 hours later still no answer to my question. TNCR sucks at maths.
|
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Mikhailoh | Dec 7 2011, 10:39 AM Post #7 |
|
If you want trouble, find yourself a redhead
|
Why would we put in $500 labor on a $1 question?
|
|
Once in his life, every man is entitled to fall madly in love with a gorgeous redhead - Lucille Ball | |
![]() |
|
| brenda | Dec 7 2011, 10:43 AM Post #8 |
![]()
..............
|
Exactly. Our time is too valuable to |
|
“Weeds are flowers, too, once you get to know them.” ~A.A. Milne | |
![]() |
|
| Axtremus | Dec 7 2011, 11:24 AM Post #9 |
|
HOLY CARP!!!
|
Because we suck at maths. |
![]() |
|
| Axtremus | Dec 7 2011, 11:27 AM Post #10 |
|
HOLY CARP!!!
|
The answer, BTW, is 293. |
![]() |
|
| sue | Dec 7 2011, 12:15 PM Post #11 |
|
HOLY CARP!!!
|
huh? |
![]() |
|
| Horace | Dec 7 2011, 12:15 PM Post #12 |
|
HOLY CARP!!!
|
Off the top of my head, and with full knowledge that if this is a good answer, people will assume I googled it, and if it's a bad answer, people will assume it came from me and that it's the best I could ever do: Nothing elegant occurs to me. Just have to brute-force it with an iteration over the combinations. A way to do it which might be slightly faster than the most naive brute force way would be to start with the lowest denomination, 1, and iterate over 1, 2, 3, 4, etc of them, finding the total sum for each, and adding each total to a lookup table of "totals" you have access to, referencing those totals against the combos of coins that can sum to them. This can be conceptualized as a simple grid with 100 rows (in this case) with each row being a growing list of combinations of coins that can sum to it. Continue with the "1" denomination and your grid will have 100 rows, each with one column: the number of pennies it takes to sum to that row's number. Stop when the sum reaches the target amount. Then move on to the next highest denomination, 5. Starting with 1, the sum is 5. Add another column to the fifth row of the grid, this time indicating that the sum of 5 can be made from a nickel. Also, note that you now need 95 to reach 100, the target, so look up the 95th row and see how many ways you have to make that. In this case, there is one way. Add the combination of the 5 and the 95 to the 100 row. Then move on to 2 nickels, and do the same. (Edit: you'd have to do that for each of the rows - after you added "1 x nickel" to the 5th row, you'd iterate over rows 1-100 and combine that nickel with all the others, adding the combination to the combination's sum's row. So row 6 would get a "1 nickel and 1 penny" entry added to it, row 7 would get a "1 nickel and 2 pennies" entry added to it, etc. Only add entries that sum to 100 or less.) Etc, iterate over all denominations up to a dollar coin, I suppose. The answer is the number of columns in the 100th row of the grid. This works for any arbitrary sum and denominations, though it would grow to be massively computationally expensive in the general case. Edited by Horace, Dec 7 2011, 12:36 PM.
|
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| somebody else's sock | Dec 7 2011, 12:25 PM Post #13 |
|
Middle Aged Carp
|
I initially read it as you did, sue. It can be parsed a second way, which is how Klaus intended it. Add the two quarters (50 cents) and the five dimes (another 50 cents)....equals a dollar. |
![]() |
|
| sue | Dec 7 2011, 12:28 PM Post #14 |
|
HOLY CARP!!!
|
Ah, yes, thanks. Gotta lose those extra zeros. |
![]() |
|
| Horace | Dec 7 2011, 12:37 PM Post #15 |
|
HOLY CARP!!!
|
Personally I like thinking about this sort of thing. Such stuff even comes up at work sometimes. |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| Klaus | Dec 7 2011, 02:07 PM Post #16 |
![]()
HOLY CARP!!!
|
How did you calculate it? Or did you just google it? |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Klaus | Dec 7 2011, 02:23 PM Post #17 |
![]()
HOLY CARP!!!
|
Here is my (rather brute force) solution, written as a Scala program: val coins = List(1,5,10,25,50,100) def solve(s: Int) : Int = count(s,coins.length-1) def count(s: Int, c: Int) : Int = if (s == 0) 1 else if ((s < 0) || (c < 0)) 0 else count(s, c-1)+count(s - coins(c), c) You can copy& paste it to http://www.simplyscala.com/ to try it out. For instance, try "solve(100)" |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Axtremus | Dec 7 2011, 05:12 PM Post #18 |
|
HOLY CARP!!!
|
Google. Think of it as retrieving a cached answer for a previously computed problem as opposed to recomputing the answer for a problem. ![]() That's one way you can look good solving a $1 answer without investing $500 in time.
|
![]() |
|
| kenny | Dec 7 2011, 05:19 PM Post #19 |
|
HOLY CARP!!!
|
The answer is 293, and I'm so smart I didn't have to Google it. I read it here. |
![]() |
|
| Horace | Dec 7 2011, 06:57 PM Post #20 |
|
HOLY CARP!!!
|
That's an elegant idea, Klaus. The general answer to the problem, as you solve it, is that (number of ways to make change for M cents with these D denominations) is (the number of ways to make change for M cents with D - Dn denominations) + (the number of ways to make change for M-Dn cents with D denominations). That's pretty cool. Here's your idea in c#: int[] coins = new int[] { 1, 5, 10, 25, 50, 100 }; int Solve(int s) { return Count(s, coins.Length - 1); } private int Count(int target, int c) { if (target == 0) return 1; else if (target < 0 || c < 0) return 0; else return Count(target, c - 1) + Count(target - coins[c], c); } Here's my top-of-my-head idea in c#: int CountCombos(int[] denoms, int targetTotal) { int[] sumsAndCombos = new int[targetTotal]; foreach (int denom in denoms) { int[] newCombos = new int[targetTotal]; for (int sum1 = denom; sum1 <= targetTotal; sum1 += denom) { newCombos[sum1 - 1]++; for (int totalSum = sum1 + 1; totalSum <= targetTotal; totalSum++) newCombos[totalSum - 1] += sumsAndCombos[totalSum - sum1 - 1]; } for (int i = 0; i < targetTotal; i += 1) sumsAndCombos[ i ] += newCombos[ i ]; } return sumsAndCombos[targetTotal - 1]; } I'd note that while yours is more conceptually elegant, it doesn't scale well computationally due to the recursion. For the given problem our solutions take about the same amount of time, but for making change for $4, yours takes about 6 times as long, and for $10, yours takes over a thousand times as long. (The answers are always identical because both solutions are correct.) A small modification to mine can output each of the 293 combinations (because I'm sure we're all dying to know): 100x1 95x1+1x5 90x1+2x5 85x1+3x5 80x1+4x5 75x1+5x5 70x1+6x5 65x1+7x5 60x1+8x5 55x1+9x5 50x1+10x5 45x1+11x5 40x1+12x5 35x1+13x5 30x1+14x5 25x1+15x5 20x1+16x5 15x1+17x5 10x1+18x5 5x1+19x5 20x5 90x1+1x10 85x1+1x5+1x10 80x1+2x5+1x10 75x1+3x5+1x10 70x1+4x5+1x10 65x1+5x5+1x10 60x1+6x5+1x10 55x1+7x5+1x10 50x1+8x5+1x10 45x1+9x5+1x10 40x1+10x5+1x10 35x1+11x5+1x10 30x1+12x5+1x10 25x1+13x5+1x10 20x1+14x5+1x10 15x1+15x5+1x10 10x1+16x5+1x10 5x1+17x5+1x10 18x5+1x10 80x1+2x10 75x1+1x5+2x10 70x1+2x5+2x10 65x1+3x5+2x10 60x1+4x5+2x10 55x1+5x5+2x10 50x1+6x5+2x10 45x1+7x5+2x10 40x1+8x5+2x10 35x1+9x5+2x10 30x1+10x5+2x10 25x1+11x5+2x10 20x1+12x5+2x10 15x1+13x5+2x10 10x1+14x5+2x10 5x1+15x5+2x10 16x5+2x10 70x1+3x10 65x1+1x5+3x10 60x1+2x5+3x10 55x1+3x5+3x10 50x1+4x5+3x10 45x1+5x5+3x10 40x1+6x5+3x10 35x1+7x5+3x10 30x1+8x5+3x10 25x1+9x5+3x10 20x1+10x5+3x10 15x1+11x5+3x10 10x1+12x5+3x10 5x1+13x5+3x10 14x5+3x10 60x1+4x10 55x1+1x5+4x10 50x1+2x5+4x10 45x1+3x5+4x10 40x1+4x5+4x10 35x1+5x5+4x10 30x1+6x5+4x10 25x1+7x5+4x10 20x1+8x5+4x10 15x1+9x5+4x10 10x1+10x5+4x10 5x1+11x5+4x10 12x5+4x10 50x1+5x10 45x1+1x5+5x10 40x1+2x5+5x10 35x1+3x5+5x10 30x1+4x5+5x10 25x1+5x5+5x10 20x1+6x5+5x10 15x1+7x5+5x10 10x1+8x5+5x10 5x1+9x5+5x10 10x5+5x10 40x1+6x10 35x1+1x5+6x10 30x1+2x5+6x10 25x1+3x5+6x10 20x1+4x5+6x10 15x1+5x5+6x10 10x1+6x5+6x10 5x1+7x5+6x10 8x5+6x10 30x1+7x10 25x1+1x5+7x10 20x1+2x5+7x10 15x1+3x5+7x10 10x1+4x5+7x10 5x1+5x5+7x10 6x5+7x10 20x1+8x10 15x1+1x5+8x10 10x1+2x5+8x10 5x1+3x5+8x10 4x5+8x10 10x1+9x10 5x1+1x5+9x10 2x5+9x10 10x10 75x1+1x25 70x1+1x5+1x25 65x1+2x5+1x25 60x1+3x5+1x25 55x1+4x5+1x25 50x1+5x5+1x25 45x1+6x5+1x25 40x1+7x5+1x25 35x1+8x5+1x25 30x1+9x5+1x25 25x1+10x5+1x25 20x1+11x5+1x25 15x1+12x5+1x25 10x1+13x5+1x25 5x1+14x5+1x25 15x5+1x25 65x1+1x10+1x25 60x1+1x5+1x10+1x25 55x1+2x5+1x10+1x25 50x1+3x5+1x10+1x25 45x1+4x5+1x10+1x25 40x1+5x5+1x10+1x25 35x1+6x5+1x10+1x25 30x1+7x5+1x10+1x25 25x1+8x5+1x10+1x25 20x1+9x5+1x10+1x25 15x1+10x5+1x10+1x25 10x1+11x5+1x10+1x25 5x1+12x5+1x10+1x25 13x5+1x10+1x25 55x1+2x10+1x25 50x1+1x5+2x10+1x25 45x1+2x5+2x10+1x25 40x1+3x5+2x10+1x25 35x1+4x5+2x10+1x25 30x1+5x5+2x10+1x25 25x1+6x5+2x10+1x25 20x1+7x5+2x10+1x25 15x1+8x5+2x10+1x25 10x1+9x5+2x10+1x25 5x1+10x5+2x10+1x25 11x5+2x10+1x25 45x1+3x10+1x25 40x1+1x5+3x10+1x25 35x1+2x5+3x10+1x25 30x1+3x5+3x10+1x25 25x1+4x5+3x10+1x25 20x1+5x5+3x10+1x25 15x1+6x5+3x10+1x25 10x1+7x5+3x10+1x25 5x1+8x5+3x10+1x25 9x5+3x10+1x25 35x1+4x10+1x25 30x1+1x5+4x10+1x25 25x1+2x5+4x10+1x25 20x1+3x5+4x10+1x25 15x1+4x5+4x10+1x25 10x1+5x5+4x10+1x25 5x1+6x5+4x10+1x25 7x5+4x10+1x25 25x1+5x10+1x25 20x1+1x5+5x10+1x25 15x1+2x5+5x10+1x25 10x1+3x5+5x10+1x25 5x1+4x5+5x10+1x25 5x5+5x10+1x25 15x1+6x10+1x25 10x1+1x5+6x10+1x25 5x1+2x5+6x10+1x25 3x5+6x10+1x25 5x1+7x10+1x25 1x5+7x10+1x25 50x1+2x25 45x1+1x5+2x25 40x1+2x5+2x25 35x1+3x5+2x25 30x1+4x5+2x25 25x1+5x5+2x25 20x1+6x5+2x25 15x1+7x5+2x25 10x1+8x5+2x25 5x1+9x5+2x25 10x5+2x25 40x1+1x10+2x25 35x1+1x5+1x10+2x25 30x1+2x5+1x10+2x25 25x1+3x5+1x10+2x25 20x1+4x5+1x10+2x25 15x1+5x5+1x10+2x25 10x1+6x5+1x10+2x25 5x1+7x5+1x10+2x25 8x5+1x10+2x25 30x1+2x10+2x25 25x1+1x5+2x10+2x25 20x1+2x5+2x10+2x25 15x1+3x5+2x10+2x25 10x1+4x5+2x10+2x25 5x1+5x5+2x10+2x25 6x5+2x10+2x25 20x1+3x10+2x25 15x1+1x5+3x10+2x25 10x1+2x5+3x10+2x25 5x1+3x5+3x10+2x25 4x5+3x10+2x25 10x1+4x10+2x25 5x1+1x5+4x10+2x25 2x5+4x10+2x25 5x10+2x25 25x1+3x25 20x1+1x5+3x25 15x1+2x5+3x25 10x1+3x5+3x25 5x1+4x5+3x25 5x5+3x25 15x1+1x10+3x25 10x1+1x5+1x10+3x25 5x1+2x5+1x10+3x25 3x5+1x10+3x25 5x1+2x10+3x25 1x5+2x10+3x25 4x25 50x1+1x50 45x1+1x5+1x50 40x1+2x5+1x50 35x1+3x5+1x50 30x1+4x5+1x50 25x1+5x5+1x50 20x1+6x5+1x50 15x1+7x5+1x50 10x1+8x5+1x50 5x1+9x5+1x50 10x5+1x50 40x1+1x10+1x50 35x1+1x5+1x10+1x50 30x1+2x5+1x10+1x50 25x1+3x5+1x10+1x50 20x1+4x5+1x10+1x50 15x1+5x5+1x10+1x50 10x1+6x5+1x10+1x50 5x1+7x5+1x10+1x50 8x5+1x10+1x50 30x1+2x10+1x50 25x1+1x5+2x10+1x50 20x1+2x5+2x10+1x50 15x1+3x5+2x10+1x50 10x1+4x5+2x10+1x50 5x1+5x5+2x10+1x50 6x5+2x10+1x50 20x1+3x10+1x50 15x1+1x5+3x10+1x50 10x1+2x5+3x10+1x50 5x1+3x5+3x10+1x50 4x5+3x10+1x50 10x1+4x10+1x50 5x1+1x5+4x10+1x50 2x5+4x10+1x50 5x10+1x50 25x1+1x25+1x50 20x1+1x5+1x25+1x50 15x1+2x5+1x25+1x50 10x1+3x5+1x25+1x50 5x1+4x5+1x25+1x50 5x5+1x25+1x50 15x1+1x10+1x25+1x50 10x1+1x5+1x10+1x25+1x50 5x1+2x5+1x10+1x25+1x50 3x5+1x10+1x25+1x50 5x1+2x10+1x25+1x50 1x5+2x10+1x25+1x50 2x25+1x50 2x50 1x100 |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| Horace | Dec 7 2011, 06:58 PM Post #21 |
|
HOLY CARP!!!
|
testing + signs Hmm, guess they just don't show up in post previews. Interesting bug. Edited by Horace, Dec 7 2011, 06:58 PM.
|
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| Klaus | Dec 8 2011, 03:46 AM Post #22 |
![]()
HOLY CARP!!!
|
Recursion is not expensive in properly implemented languages (which excludes C# )What makes my code slow is just that it performs the same computations many times; a simple cache is sufficient to take care of that. Here is a slight variant of my code with caching that is exponentially faster.
For instance, it can(*) compute the number for $5000 in a fraction of a second: solve(500000) = 4813817521260169269 The variant you proposed seems to be a kind of dynamic programming version of the problem, but I assume that my version with caching may be even faster because it will not compute the solutions for all amounts less than the original amount. Your solution is equivalent to filling the cache for all combinations of amount and #coins, whereas my solution will only fill the cache with those entries needed for the particular given amount. Edit: I tried your variant as well and it confirms my suspicion: For $1000 it needs several seconds, and for $5000 I had to kill the process after two minutes. But it is still cool that you managed to find a different correct solution! Recursive divide&conquer is so deeply baked into my brain that I suck at imperative&iterative solutions ![]() (*)when changing int to long and increasing the stack size |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| apple | Dec 8 2011, 04:34 AM Post #23 |
|
one of the angels
|
math is for the birds |
| it behooves me to behold | |
![]() |
|
| Klaus | Dec 8 2011, 08:29 AM Post #24 |
![]()
HOLY CARP!!!
|
If you are not quiet I'll post all 4813817521260169269 possibilities of coin sets whose value is $5000! |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| kenny | Dec 8 2011, 08:33 AM Post #25 |
|
HOLY CARP!!!
|
... and some of them birds are very smart. I did very well in math till I got to calculus. I just couldn't integrate it into my brain.
|
![]() |
|
| Go to Next Page | |
| « Previous Topic · The New Coffee Room · Next Topic » |
- Pages:
- 1
- 2









6:44 AM Jul 11