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 <[email protected]>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 <
> [email protected]> wrote:
>
>> This seems to be Coin Change problem. Just google that.
>>
>>
>> On Tue, May 28, 2013 at 12:42 AM, Adolfo Ccanto <[email protected]>wrote:
>>
>>> Can you write the constraints for this problem?
>>> thanks.
>>> Adolfo
>>>
>>>
>>> 2013/5/18 rahul sharma <[email protected]>
>>>
>>>> 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 [email protected].
>>>>
>>>>
>>>>
>>>
>>> --
>>> 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 [email protected].
>>>
>>>
>>>
>>
>>
>>
>> --
>> 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 [email protected].
>>
>>
>>
>
> --
> 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 [email protected].
>
>
>
--
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 [email protected].
