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