@amol knapsack is originaly a greedy problem only!!!!!!!!The spirit remains the same,selecting the best at each step....Dp helps in defining the best in the particular case. @Gaurav I think its NP complete once the number of teams become varaible,,,,, corrct me if wrong i am weak with the theoritical stuffs...
On Thu, Aug 4, 2011 at 8:06 PM, Amol Sharma <[email protected]> wrote: > @gaurav: agree...greedy wouldn't work in this case......even 0-1 knapsack > is a DP problem...which can't be done by greedy !! > -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > > > > > On Thu, Aug 4, 2011 at 7:46 PM, Gaurav Menghani <[email protected] > > wrote: > >> On Thu, Aug 4, 2011 at 7:42 PM, Gaurav Menghani >> <[email protected]> wrote: >> > >> > On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh <[email protected]> >> wrote: >> >> >> >> Its a classical 0/1 knapsack problem which can be implemented either as >> a >> >> greedy solution or dp,,,, >> > >> > It has been stated earlier in the thread that this is an 'NP-Complete' >> > problem. [0] >> > It means, there is no known polynomial-time algorithm for this problem. >> If >> > you think you have a greedy solution to this problem, think again. The >> DP >> > solution is also, 'pseudo-polynomial-time' >> >> Just adding, greedy solutions are always possible, but the thing to >> ponder over is, whether they give optimal solutions _for_every_case_ >> or not. >> >> >> -- >> Gaurav Menghani >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
