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
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.