find the minimum number of sets

Question

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

• S₁ = {2,3}
• S₂ = {2, 5}
• S₃ = {4, 5}
• S₄ = {4}
• S₅ = {5}

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

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

Isn't it a kind of knapsack problem?

• gnat: please don't cross-post : stackoverflow.com/questions/27771682/…
• Wolf: @gnat Will this question survive or the one on SO, or both?
• gnat: @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)
• maple_shaft: 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.

Answer 1

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.