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 <[email protected]>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 <[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]. > -- 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].
