Let me first explain the problem using an analogy.

Lets say you have N doors and M keys. Each door can be opened with a combination of keys, each combination is also unique (ie. there wont be two doors that are opened with same combination). For an example to open Door 1 you need all of these key:s A, B and C.

Door 2 can be opened using keys: C, F, G, E and T etc. All doors are accessible(there are no doors behind another door).

Now the question is: If you can chose k keys such that k < M, which keys should be picked so that with that combination of keys you can open more doors than with any other combination of k keys.



This kind of problem cant be solved with exhaustive search since in my case there are 100 keys and just generating all combinations would take centuries (there would be around 5.5E20 combinations if k=20).



Im not too knowledgeable in algorithms but this seems like some kind of constraint satisfaction problem but not exactly. Anyway Im kind of stuck. If I could just figure out what kind of problem this is and what its called I might just be able to solve this thing in less than a century.