tag:blogger.com,1999:blog-19303585.post2774746791817123777..comments2019-12-11T14:12:28.609+00:00Comments on John Graham-Cumming: The minimum coin problem (with prize)Unknownnoreply@blogger.comBlogger17125tag:blogger.com,1999:blog-19303585.post-52388583105797653992013-08-27T03:09:41.610+00:002013-08-27T03:09:41.610+00:00Here coin change problem is imoplemented in java a...Here coin change problem is imoplemented in java and its realy easy to understand.<br />http://placementjump.blogspot.in/2013/08/coin-change-problem-in-java-dynamic.html<br /><br />int minimum(int x,int y,int z){<br /> int min;<br /> if(x>=y && z>=y)<br /> return y;<br /> else<br /> if(x>=z)<br /> return z;<br /> else<br /> return x;<br /> <br /> <br /> }placement jumphttps://www.blogger.com/profile/12653699121977386019noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-8645249684000994002013-05-14T11:47:05.519+00:002013-05-14T11:47:05.519+00:00This comment has been removed by the author.Matt Hickfordhttps://www.blogger.com/profile/05524405196430062750noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-78936790006087725642013-05-11T19:10:21.390+00:002013-05-11T19:10:21.390+00:00This comment has been removed by the author.Matt Hickfordhttps://www.blogger.com/profile/05524405196430062750noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-11618562463445060102013-05-11T19:10:04.984+00:002013-05-11T19:10:04.984+00:00I remember reading a similar problem 'pay with...I remember reading a similar problem 'pay with as few coins as possible' in the wonderful book The Algorithm Design Manual. Cashiers know the greedy algorithm (keep using the biggest coin you can) is optimal for British currency. However imagine trying to pay 6 in a fictional currency with denominations [4,3,1]. The greedy algorithm gives 4+1+1 which isn't as good as 3+3. I don't know if any real world currencies are so perverse.<br /><br />This problem is cool too. Allowing overpayment stumped me for a while. By the way, I'm not sure the constraint "he should not be able to return any to me without the sum of the remaining coins dropping below £1.70" is correctly reproduced in the mathematical statement 'problem 2' (it should be a constraint rather than mixed in with the utility function).<br /><br />Anyway, here are my solutions (Python) to the exact problem and the allowing change problem. The wonderthought was that you can solve the allowing change problem by solving the exact problem for varying amounts of overpay. Just be careful only to use coins bigger than the amount you overpay, so not to break the change constraint.<br /><br />https://gist.github.com/matt-hickford/5560996<br /><br />@Michael sometimes it is optimal to overpay:<br /><br /> An example where you can use more coins by paying more than asked<br /> Pay 14 with coins [5, 5, 5, 7, 7]<br /> sum([7, 7]) = 14 # can only use 2 coins, if being exact <br /> sum([7, 5, 5]) = 17 # can use with 3 coins, if overpayingMatt Hickfordhttps://www.blogger.com/profile/05524405196430062750noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-81769675555056727392013-04-25T06:10:53.037+00:002013-04-25T06:10:53.037+00:00I did it with Octave:
https://github.com/panatoli...I did it with Octave:<br /><br />https://github.com/panatoli/coin_problem<br />Anatoli Plotnikovhttps://www.blogger.com/profile/07564728391884959366noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-80516897315963023882013-04-24T12:06:54.873+00:002013-04-24T12:06:54.873+00:00vext, this is not a non-linear problem, it is a li...vext, this is not a non-linear problem, it is a linear programming problem with integer constraints. Perhaps you meant you didn't know GLPK could solve integer programming problems?Josh Jordanhttps://www.blogger.com/profile/11389483538911210732noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-56891388646320664562013-04-24T09:48:20.874+00:002013-04-24T09:48:20.874+00:00Hah, I didn't know GLPK could solve non-linear...Hah, I didn't know GLPK could solve non-linear problems. Today I learned...vext01https://www.blogger.com/profile/15706547304880185129noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-74135508220247200542013-04-24T03:17:43.736+00:002013-04-24T03:17:43.736+00:00These can be straightforwardly posed and solved as...These can be straightforwardly posed and solved as integer programming problems with a solver such as GLPK.<br />http://www.takingthefun.com/2013/04/john-graham-cunnings-minimum-coin.html<br />Problem 1: http://pastebin.com/2hB9KWCx<br />Problem 2: http://pastebin.com/Dh6NWVaD<br />Problem 3: http://pastebin.com/42dmp4VMJoshhttps://www.blogger.com/profile/11389483538911210732noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-53396986752559353152013-04-24T02:52:39.673+00:002013-04-24T02:52:39.673+00:00GLPK is a nice MINLP solver. The syntax seems pre...GLPK is a nice MINLP solver. The syntax seems pretty reasonable as well. This is the first time I've used it, so this almost certainly isn't optimal:<br /><br />set COINS;<br /><br />param Value {i in COINS};<br />param Count {i in COINS};<br /><br />var x {i in COINS} >=0, integer;<br /><br />maximize z: sum{i in COINS} x[i];<br /><br />s.t. Payout: sum{i in COINS} Value[i]*x[i] >= 170;<br />s.t. Use {i in COINS} : x[i] <= Count[i];<br />s.t. Enough {i in COINS} : sum{j in COINS} Value[j]*x[j] <= 169 + Value[i];<br /><br />data;<br /><br />set COINS := twolb onelb fiftyp twentyp tenp fivep twop onep;<br /><br />param Value:= twolb 200 onelb 100 fiftyp 50 twentyp 20 tenp 10 fivep 5<br /> twop 2 onep 1;<br /><br /><br />param Count:= twolb 1 onelb 2 fiftyp 2 twentyp 3 tenp 1 fivep 2 twop 2<br /> onep 2;<br /><br />end;<br />Dubyahttps://www.blogger.com/profile/17525985941706401908noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-55679496064042905992013-04-23T16:11:20.628+00:002013-04-23T16:11:20.628+00:00This reckon this can be solved as a mixed-integer ...This reckon this can be solved as a mixed-integer non-linear programming problem:<br /><br />maximise: c1 + c2 + ... + c14 + c15;<br /><br />gave = 200 * c1 + 100 * c2 + ... + 1 * c14 + 1 * c15;<br /><br />change = gave - 170;<br /><br />c1 * change <= 199;<br />c2 * change <= 99;<br />c3 * change <= 99;<br />c4 * change <= 49;<br />c5 * change <= 49;<br />c6 * change <= 19;<br />c7 * change <= 19;<br />c8 * change <= 19;<br />c9 * change <= 9;<br />c10 * change <= 4;<br />c11 * change <= 4;<br />c12 * change <= 1;<br />c13 * change <= 1;<br />c14 * change <= 0;<br />c15 * change <= 0;<br /><br />where c1, ..., c15 are binary decision variables.<br /><br />I think this is correct, but I don't have a MINLP solver set up to try it. They tend to have a lot of obscure dependencies that need to be built by hand...<br />vext01https://www.blogger.com/profile/15706547304880185129noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-51842568150936394052013-04-23T15:28:51.235+00:002013-04-23T15:28:51.235+00:00I know this is supposed to be a thought experiment...I know this is supposed to be a thought experiment :) , but coins are a poor form of currency. <br /><br />Heavy fiddly and easily not there when you need them ... also there is an apparent need for an algorithm to describe how to best get rid of them :)<br /><br />May I suggest some form of NFC payment ? preferably directly from a bank account and not through VISA or MASTERCARD ,adopted at least on a country level if not at a world wide level.Alex Apetreihttps://www.blogger.com/profile/00626185183079878524noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-60197605490173689902013-04-23T13:52:55.569+00:002013-04-23T13:52:55.569+00:00This comment has been removed by the author.Asger Drewsenhttps://www.blogger.com/profile/05641210218333719250noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-73970839581563336892013-04-23T13:52:28.918+00:002013-04-23T13:52:28.918+00:00Here's my solution in python: https://gist.git...Here's my solution in python: https://gist.github.com/Tyilo/5443729Asger Drewsenhttps://www.blogger.com/profile/05641210218333719250noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-22577786215296649952013-04-23T13:29:50.264+00:002013-04-23T13:29:50.264+00:00Find my solution here:
https://gist.github.com/mi...Find my solution here:<br /><br />https://gist.github.com/mihi-tr/5443534<br /><br />I do think (untested) that spending the exact number of coins has you _always_ ending up with less coins (in this combination)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-19303585.post-29953777588078596332013-04-23T11:44:30.306+00:002013-04-23T11:44:30.306+00:00Yes it looks identical, other than the fact that y...Yes it looks identical, other than the fact that you can go over 1.70 by no more than one coin.William Sewellhttps://www.blogger.com/profile/05145080453341944629noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-68481722840095141522013-04-23T11:43:55.349+00:002013-04-23T11:43:55.349+00:00Maybe dynamic programming will work for number one...Maybe dynamic programming will work for number one?<br /><br />d = [ 1, 2, 5, ...] # coin values<br />x = [ 2, 2, 2, ...] # number of coins you have<br />goal = 170 # how much we are paying<br /><br />a[1][1] = [1, 0, 0, ...] # assuming we start with a one piece<br />for y in range(goal):<br /> for x in range(len(d)):<br /> v = [i*j for i,j in zip(d,a[1][y])] + d[x]<br /> if v == goal:<br /> a[1][y][x] = a[1][y-1][x] + 1<br />print a[1][goal - 1]<br /><br />Matthttps://www.blogger.com/profile/06928988782301753297noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-61904280582427481972013-04-23T11:03:13.117+00:002013-04-23T11:03:13.117+00:00This looks suspiciously like The Knapsack Problem....This looks suspiciously like <a href="http://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow">The Knapsack Problem</a>.zimpenfishhttps://www.blogger.com/profile/02878173289281662062noreply@blogger.com