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.
