thnkx everybody for help but now i come to know that constraint on money is <10^9..now in this situation we can't use DP.. once again i m mentioning the question ....... given k number of coins (v1,v2,v3,......vk) and sum S .now we have to find out that is it possible to exchange the money using these coin.if posible then print YES otherwise NO. k<100 and S<10^9...so with this constraints i don't think tabular solution is possible ....... need attention of algorithm experts ...
On 3/4/07, algogeeks group <[EMAIL PROTECTED]> wrote: > > > Algorithm Geeks > http://groups.google.com/group/algogeeks > > algogeeks@googlegroups.com > > Today's topics: > > * dynamic programming .. - 3 messages, 3 authors > > http://groups.google.com/group/algogeeks/browse_thread/thread/97b191e8e6427c82 > * how to tell honest people - 2 messages, 2 authors > > http://groups.google.com/group/algogeeks/browse_thread/thread/ab8c5aff76201e43 > > > ============================================================================== > TOPIC: dynamic programming .. > > http://groups.google.com/group/algogeeks/browse_thread/thread/97b191e8e6427c82 > > ============================================================================== > > == 1 of 3 == > Date: Sun 4 Mar 2007 00:24 > From: "mukesh tiwari" > > > 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 > > > > > == 2 of 3 == > Date: Sat 3 Mar 2007 11:58 > From: "aditi saha" > > > 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 > > > > > > > > > > > > == 3 of 3 == > Date: Sun 4 Mar 2007 03:38 > From: "Sandesh" > > > Hi, > Greedy solution will work only when the denomination of coins are such > that they are > multiples of the smallest number present (it should be greater than 1) > > In dynamic programming we check all possible combination. > and improve the runtime by storing results in tables/arrays we can > save a lot of computation. > > Here- > Generate all possible combination of numbers, allowing > repetition and > suppose you say 'nCr' then 'r' running from 1 to n. > > > > On Mar 3, 11:54 pm, "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 > > > > > > > > ============================================================================== > TOPIC: how to tell honest people > > http://groups.google.com/group/algogeeks/browse_thread/thread/ab8c5aff76201e43 > > ============================================================================== > > == 1 of 2 == > Date: Sat 3 Mar 2007 15:41 > From: "learner" > > > Hi, I was stuck by the follwoing interesting problem, any idea to > solve it? > 100 people total, some honest and some not. > honest will always say the truth. > not hosest will sometimes lie. > and honest people is more than not-honest ones. > > You can ask any people the following > question about any other people : "Professor Y , is Professor X > honest?" Professor > Y will answer with either "yes" or "no." Design an algorithmthat, with > no more than > 198 questions, would allow you to figure out which of the 100 > professors are honest > > > > > > == 2 of 2 == > Date: Sat 3 Mar 2007 20:22 > From: "Karthik Singaram L" > > > Hi, > Note that the problem is solved if you find one honest professor then > you > can ask him about all the other professors and solve it 99 questions from > there on. The problem is to find one honest person in 99 questions. > This can be done as follows, > > Divide the professors into groups of 2. > > In each group ask if the opposite professor is honest. > 4 possibilities > (i) Both honest and say both honest or Both liars and say both liars > Discard all the other groups > > Choose one person from the groups saying both honest. > Observe that now whenever both are honest or both are liars in a group > one of them will get included and therefore the teams that got discarded > atleast have one liar. > In the resulting problem with 50 members still again the majority are > honest professors > > Therefore after one round (50 questions) > For second round you have (25 questions) > 50+25+(12+1)+6+(3+1)+1 = 99 questions > (whenever we have odd number of ppl it takes 1 extra question to > eliminate > the extra guy). > > So we will have the person we are looking for in 99 questions. Then ask > him about the remaining 99 ppl and you are done with exactly 198 > questions.. > > I am not sure if the exact calculations are correct for each round but > overall this is the logic > > > > > > ============================================================================== > > 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 or visit > http://groups.google.com/group/algogeeks > > To unsubscribe from this group, send email to > [EMAIL PROTECTED] > > To change the way you get mail from this group, visit: > http://groups.google.com/group/algogeeks/subscribe > > To report abuse, send email explaining the problem to > [EMAIL PROTECTED] > > > ============================================================================== > Google Groups: http://groups.google.com > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
