Ok, so you have an oracle that gives you the answer for any SUBSET-SUM (the decision problem) instance in O(n), and you want to use it to actually construct the solution. It's obvious that you can construct the solution in O(n^2) (at most n queries to the oracle). Start with the initial set S. Query the oracle with <S, k> as input to see if there is a solution. If not, you're done. Otherwise, remove some element x from S and query the oracle on <S', k>. If the oracle says yes, then you can throw away x (there is a subset of S' that sums to k), otherwise add it to the solution and update k to k - x. Continue this way until k becomes 0.
On Mar 30, 2:11 pm, "Mahdi" <[EMAIL PROTECTED]> wrote: > OK. that is the assumption of the problem that this is done in O(n). > Perhaps it is imaginary. > The Question is : > assuming this algorithm and using that, now we want to find the exact > members that their sum equals to K, with the best order. > Thank you. > > On Mar 30, 7:38 pm, "Muntasir Azam Khan" <[EMAIL PROTECTED]> > wrote: > > > On Mar 30, 10:07 pm, "Muntasir Azam Khan" <[EMAIL PROTECTED]> > > wrote: > > > > ----- Original Message ----- > > > From: "Mahdi" <[EMAIL PROTECTED]> > > > To: "Algorithm Geeks" <[email protected]> > > > Sent: Friday, March 30, 2007 1:27 PM > > > Subject: [algogeeks] Sum of subsets > > > > > We have set named S. We assume we have an algorithm that specifies if > > > > there is a subset in S that sum of it's elements equals to K in O(n) > > > > and returns TRUE or FALSE. The question is : > > > > How can we find the elements of this subset? What is the best solution > > > > with minimum order? > > > > Thanks. > > > > The best I can come up with is a O(n^2) solution. To me this looks like a > > > variation of the 0-1 knapsack problem. Could you please elaborate on how > > > you > > > are checking in O(n)? > > > > Muntasir > > > Just a *small* correction to my earlier post. This problem is actually > > NP-complete. My O(n^2) solution works only if all the members of the > > set are positive integers. > > > Muntasir --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
