The 0-1 knapsack problem is still the knapsack problem. Don On Aug 26, 1:55 pm, Piyush Grover <[email protected]> wrote: > it's similar to knapsack but not the same. In knapsack, types of items are > limited and we play on the quantity of each item. > Here each element will come once in the subset. > > On Fri, Aug 26, 2011 at 11:49 PM, Don <[email protected]> wrote: > > @rahul > > Your code will only find pairs which sum to k. The problem is to find > > a subset of as many elements in the array as required to sum as close > > as possible to k. > > It is a well-known problem and after years of study, no polynomial > > solution is known. There are reasonably fast solutions for small > > inputs, but the best anyone has done is a pseudo-polynomial-time > > algorithm using dynamic programming. Thus it is weakly NP-complete. As > > n gets large, the time required increases exponentially. > > Search the web for "Knapsack problem" to learn more. > > Don > > > On Aug 26, 1:04 pm, rahul sharma <[email protected]> wrote: > > > yes it will.... > > > return in c return 1 value at tym... > > > ijust given the code snipet....just modify it......store trhm in some > > > other array like the....but it will > > > > On Aug 26, 11:02 pm, Piyush Grover <[email protected]> wrote: > > > > > @rahul...I'm unsure if your algo returns all the subsets. > > > > > On Fri, Aug 26, 2011 at 11:24 PM, rahul sharma < > > [email protected]>wrote: > > > > > > yeah can be done in poly tym also...but we dnt knw whether we have > > > > > unsorted arry....it is possible in sorted array. > > > > > > On Aug 26, 10:52 pm, Don <[email protected]> wrote: > > > > > > This is the knapsack problem. > > > > > > Find a polynomial-time solution and you will be a hero. > > > > > > Don > > > > > > > On Aug 26, 12:43 pm, Piyush Grover <[email protected]> > > wrote: > > > > > > > > Here is a problem: > > > > > > > > Given an array of size n. Find all the MAXIMAL subsets whose sum > > is <= > > > > > K. > > > > > > > The solution is not a concern, the optimization is required. > > > > > > > > -piyush > > > > > > -- > > > > > 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.
-- 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.
