I have about 1000 sets of size <=5 containing numbers 1 to 100.
{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ...
Is it possible to find a set of size 20 that contains the maximum number of given sets?
Checking each of 100!/(80!*20!)
sets, is inefficient.
I am not so sure this is NP complete.
Consider the related problem where we get a reward of x for each set, but have to pay a price of y for each number that we want to allow. (A set only pays the reward if all the numbers it contains have been paid for.)
You can solve this type of problem using the max flow algorithm by:
Solving the maximum flow problem on this graph (from the source to destination node) finds a minimum cut cost c.
The net amount of money we would make would be N.x-c (where N is the number of sets).
If we can choose y (e.g. by bisection) such that we have selected exactly 20 numbers, then we have managed to solve for the maximum number of sets with 20 numbers.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With