2
$\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 Answer 1

2
$\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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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