It can be solved using DP
here is the recurrence eqn:-
coin[ i ] = 1+coin[ i - denom( j ) ] if i >=1 and 1< j <ArrayLen(denom)
base cases :- c[ i ]= inf if j < 0
c[ i ] = 0 if j==0
On 12/23/12, Dave <dave_and_da...@juno.com> wrote:
> @Shady. That still didn't answer my question. Maybe I didn't frame it very
> well, so let me try again. Are you naming coins that you have one of or an
> infinite supply of? I.e., if you want to use two of a coin to make a
> certain sum, does it count in the N as one coin or two? More specifically,
> if I want to make 7 as (5,1,1), do I list the coins as (1,5), which is N=2,
>
> or (1,1,5), which is N=3?
>
> Dave
>
> On Saturday, December 22, 2012 4:34:24 AM UTC-6, shady wrote:
>
>> 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 <dave_an...@juno.com
>> <javascript:>>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 ?
>>>>
>>> --
>>>
>>>
>>>
>>
>>
>
> --
>
>
>
--
