The 0-1 knapsack problem is still the knapsack problem. Don On Aug 26, 1:55 pm, Piyush Grover <piyush4u.iit...@gmail.com> 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 <dondod...@gmail.com> 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 <rahul23111...@gmail.com> 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 <piyush4u.iit...@gmail.com> wrote: > > > > > @rahul...I'm unsure if your algo returns all the subsets. > > > > > On Fri, Aug 26, 2011 at 11:24 PM, rahul sharma < > > rahul23111...@gmail.com>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 <dondod...@gmail.com> 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 <piyush4u.iit...@gmail.com> > > 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 algogeeks@googlegroups.com. > > > > > To unsubscribe from this group, send email to > > > > > algogeeks+unsubscr...@googlegroups.com. > > > > > 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 algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
