@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.
