1
$\begingroup$

Let's say a procedure called 'decision(x,q)' is available as a 'black box' X is the input set and Q is a real number Q.

I need to design an algorithm that reports "yes" if there exists a subset of X whose total sum is = Q otherwise, it reports "no".

Running time is not an issue, it just needs to have all actual numbers in the subset and it can't make more than O(n) calls to the procedure.

I believe this can be solved with dynamic programmming.

$\endgroup$
1
$\begingroup$

I believe you have misunderstood the question. You are given a black box that can answer queries of the form "does $X$ have a subset summing to $Q$", and you need to construct an algorithm that given $X$ and $Q$, finds a subset summing to $Q$ if one exists.

Here is a hint:

Choose an arbitrary $x \in X$. Ask the black box whether there is a subset of $X - x$ summing to $Q - x$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. Could I approach this with a simple knapsack approach? $\endgroup$ – user21996 Nov 5 '14 at 3:13
  • $\begingroup$ I don't know what a simple knapsack approach is, but if you succeed, then it's possible. $\endgroup$ – Yuval Filmus Nov 5 '14 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.