Hi mukesh, Let M(S),S>=0 be true if its possible to make money S with the given coins v1,v2,...vk. Then, M(S)=M(S-v1) || M(S-v2) || ...|| M(S-vk). Base Case: M(vi)=true for 1<=i<=k. M(0)=true Let vl be the smallest of all vi's where 1<=i<=k. Then M(1...vl-1)=false.
On 3/3/07, mukesh tiwari <[EMAIL PROTECTED]> wrote: > > hi everybody ..i am stuck on a problem ..i need ur help.. > problem is that i have k coins(v1,v2,v3......vk) and money S . and i have > to find out that whether it is possible or not to make the money S using > the given coins...firstly i was using greedy but it failed on some inputs > ..like we have 2 coins of (3 and 5) and i have to exchange 11 . > so using greedy fiirstly i take 5 since it is less than 11 so i have to > again take 5 and sum becomes 10 . So using greedy it gives it not possible > but if use onr coin of 5 and two coin of 3 then it is possible .. > so plz help me dynamic programming experts.. > limits are k<100 and S<50000 > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
