3
$\begingroup$

I'm interested in finding maximal solutions to the problem of finding a subset that "sums" to a specific value. The elements of the set are boolean vectors and the notion of "sum" is point-wise or.

Say you had {10, 01, 00} then there are two subsets that sum to 11: {10, 01} and {10, 01, 00}.

In particular, I want maximal solutions. So I don't care about {10, 01} if {10, 01, 00} is a solution, because {10, 01, 00} contains {10, 01}.

What algorithms are known for how to do this? Can you think of an algorithm? One way to do this would be to use the dynamic programming solution mentioned on Wikipedia (modifying it to store maximal sets of subsets rather than true/false): Pseudo-polynomial time dynamic programming solution

Is there something that beats this due to using vectors rather than integers? Or is this doomed to be just as inefficient?

$\endgroup$
  • $\begingroup$ What means "pointwise or"? Does it mean to "or" the coordinates of the binary vectors? If so, I think the solution of Yuval will not work, e.g. 01+11=10, but 01 !<=10 and 11 !<= 10 $\endgroup$ – miracle173 Aug 1 '16 at 6:31
7
$\begingroup$

Let us say that $x \leq y$ if $x_i \leq y_i$ for all $i$. Suppose that your starting vectors are $x_1,\ldots,x_n$ and your target is $y$. If $x_i \not\leq y$ then $x_i$ cannot belong to any solution, so you can throw away all these vectors. The remaining vectors OR together to a vector $x \leq y$. If $x \neq y$ then there is no solution. Otherwise, take all remaining vectors – this is clearly the maximal solution.

$\endgroup$
  • 1
    $\begingroup$ Wow that's crazy efficient. This is fantastic news for me! There is also one maximal subset which is even better! $\endgroup$ – Jake Jul 31 '16 at 21:00

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.