3 ms·
The minimum coin problem (with prize)
- dreen 14y agoIf the reason to use most coins is to get rid of change you'd better just put all coins in self service tesco checkout and let the till give out change in minimum amount of coins automatically. (yes I know thats not the point)
- jgrahamc 14y agoI agree that that's not the point, but that's a nice hack.
- shawabawa3 14y agoI've actually found that the tesco machines are sneaky, they seem to give change in what they have excess of. I actually did this yesterday, dumped all my coins in and needed 40p change. I got 8 5p's back
- dreen 14y agoYou might be right, it would make sense. Thank gods for those tills anyway, I dont know what I would do with my change without them. edit: challenge: find a way to guess balances of each coin nominal in the machine by paying with specific coins yourself.
- shabble 14y agoIf I'm interpreting the 'reasonable excess' requirement correctly, I think you can get a total sum of 3 coins? Lbh cnl jvgu bar gjb-uhaqerq cyhf bar gjragl, naq erprvir bar svsgl-crapr va punatr. Edit: Duh, on re-reading I totally misunderstood, you're trying to minimise YOUR remainign coins, not the number used in the transaction. Back to the REPL'in board. [1] http://www.rot13.com/index.php http://www.rot13.com/index.php
- ronaldx 14y agoRegarding the 'bonus' problem on weight of coins: 1p and 2p coins of the same value weigh the same, by design. Similarly 5p and 10p.
- zeteo 14y agoWe can easily reduce subset sum [1] to Problem 1 by using the second formulation ("given a set of integers and an integer s, does any non-empty subset sum to s?") and setting the integers to be the coin denominations and all the corresponding x_i equal to 1. So Problem 1 is NP-hard. [1] http://en.wikipedia.org/wiki/Subset_sum_problem http://en.wikipedia.org/wiki/Subset_sum_problem