1

Let's explain my question with example I have some integer sets for example

  • S1 = {2,3}
  • S2 = {2, 5}
  • S3 = {4, 5}
  • S4 = {4}
  • S5 = {5}

And I have sample set Ssample with 4 elements {2, 3, 4, 5}.

So now I want to find minimum number of sets to build Ssample. In this case I can use S1 and S3 because S1 contains {2, 3} and S3 contains {4, 5}. Their union is equivalent to Ssample. We can choose sets S1, S4, and S5 but that isn't a sufficient answer so how can find this minimum number of sets?

Isn't it a kind of knapsack problem?

4
  • 2
    please don't cross-post: stackoverflow.com/questions/27771682/…
    – gnat
    Jan 5, 2015 at 0:08
  • @gnat Will this question survive or the one on SO, or both?
    – Wolf
    Jan 5, 2015 at 13:27
  • @Wolf I believe it's a better fit here. Although it's up to our and SO moderators to sort this out (I flagged it for their attention)
    – gnat
    Jan 5, 2015 at 17:07
  • 1
    I flagged for closure at StackOverflow. In the future OP algorithm questions are better suited for this site over StackOverflow however you have the choice to post at one or the other. Don't cross post questions across sites unless they are tailored to the sites audience.
    – maple_shaft
    Jan 6, 2015 at 3:30

1 Answer 1

4

It's similar to the knapsack problem in that it is NP-complete. This particular instance is the Set Cover Problem. There are a number of ways to solve this but only by approximation. Integer Linear Programming yields a reasonably fast method of approximation.

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.