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?

  • 2
    please don't cross-post: stackoverflow.com/questions/27771682/… – gnat Jan 5 '15 at 0:08
  • @gnat Will this question survive or the one on SO, or both? – Wolf Jan 5 '15 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 '15 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 '15 at 3:30
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.

| improve this answer | |

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.