We have *all kinds of denominations (1, 2, 3,.... R)*... therefore to cover this range, we generally select coins like this 1, 2, 4, 8, 16... but in this case... we can select* any N coins from R*, such that it *minimizes the average coins used for all values in the range R*... like .....
6 can be represented by 2, 4 15 -> (1, 2, 4, 8) 10 -> (2, 8) On Sat, Dec 22, 2012 at 1:59 PM, Dave <[email protected]> wrote: > @Shady: I'm not sure what you mean by "output N coins." With U.S. coins, > you can need up to 4 pennies, 1 nickel, 2 dimes, 1 quarter, and 1 > half-dollar (or 4 pennies, 1 nickel, 2 dimes, and 3 quarters, if you don't > use half-dollars, which are uncommon) to make any amount from 1 to 99 > cents. So should you output distinct coins (1,5,10,25,50), or repeat the > coins the required number of times (1,1,1,1,5,10,10,25,50)? > > Dave > > On Friday, December 21, 2012 4:01:52 PM UTC-6, shady wrote: > >> Given R and N, output N coins in the range from 1 to R such that average >> number of coins needed to represent all the number in the range is >> minimized. >> >> Any idea ? hints ? >> > -- > > > --
