A good solution for this can be seen at this
link<http://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_04_-_Minimum_no_of_coins_to_make_a_sum.jsp>
On Wed, Apr 23, 2014 at 12:42 AM, bujji jajala <jajalabu...@gmail.com>wrote:
> Hi Dave/ Ravi Rajan,
>
> I think If conditions that Dave has
> mentioned are satisfied, greedy approach can be proved to work
> with help of induction. I tried to prove with coin denominations 1 and 3.
>
> f(n) = min coins required to get change for n rupees with one rupee and 3
> rupee coins(:-) only.
> f(0) =0
> Necessary condition for greedy approach to give optimal solution.
> f(n-3) >= f(n-1) whenever n > =3
>
> f(m) <= f(m+2) for all m> 1
>
> Assumption:
> The f(m) <= f(m+2) condition holds for all m <=N
> ----------------------(1)
>
> F(N+1) = min { 1+ f(N), 1+ f(N-2) } = 1+f(N-2) ( This follows with
> induction assumption (1) ) -------------(2)
>
> f(N+3) = min{ 1+ f(N+2), 1+ f(N) } = 1+ f(N) ( This too follows with
> induction assumption (1) ) -------------(3)
>
> (2) and (3) imply
>
> f(N+1) <= f(N+3)
>
> Verifying base conditions is simple.
>
> Please let me n=know if there is any flaw in proof.
>
> @Dave Can you give some intuition behind your statement?
>
> -Thanks
> Bujji
>
>
>
>
> On Wed, May 29, 2013 at 8:54 PM, Ravi Ranjan <ravi.cool2...@gmail.com>wrote:
>
>> @DAve
>>
>> any proper reason or link to proof that at least twice can be solved
>> using greedy but others are not??
>>
>>
>> On Tue, May 28, 2013 at 12:41 PM, Shashwat Kumar <
>> shashwatkmr....@gmail.com> wrote:
>>
>>> This seems to be Coin Change problem. Just google that.
>>>
>>>
>>> On Tue, May 28, 2013 at 12:42 AM, Adolfo Ccanto <adol...@gmail.com>wrote:
>>>
>>>> Can you write the constraints for this problem?
>>>> thanks.
>>>> Adolfo
>>>>
>>>>
>>>> 2013/5/18 rahul sharma <rahul23111...@gmail.com>
>>>>
>>>>> Minimum of coins to sum s
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>>>
>>>>>
>>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> Shashwat Kumar
>>> Third year Undergraduate student
>>> Department of Computer Science and Engineering
>>> IIT Kharagpur
>>>
>>>
>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>
>>>
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>>
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
