Geek Answers Handbook

Fixed size containing the maximum number of preset sets

I have about 1000 sets of size <= 5 containing numbers from 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 size set 20 that contains the maximum number of given sets?

Checking each set 100!/(80!*20!) inefficient.

+7
set algorithm
source share
1 answer

I am not sure if this is NP complete.

Consider a related problem, where we get a reward for x for each set, but have to pay the price y for every number we want to resolve. (The set only pays a reward if all of its numbers have been paid.)

You can solve this problem using max flow algorithm :

  • Node source setting
  • Node destination setting
  • Configure node for each set
  • Setting node for each number
  • Add edge from source to each set with capacity x
  • Add edge from each number to dest with capacity y
  • For each number a in the set s add an edge from s to with infinite capacity

Solving the maximum flow problem on this graph (from source to destination node) finds the minimum cost of reduction c.

The net amount of money we would make would be Nx-c (where N is the number of sets).

If we can choose y (for example, by dividing in half), so that we have chosen exactly 20 numbers, then we managed to solve for the maximum number of sets with 20 numbers.

+1
source share

More articles:


All Articles