Return to Question

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 3 keys: A, B and C. For Door 2 you need 5 keys: C, F, G, E and T. 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.

Let me first explain the problem using an analogy.

Let's say you have $N$ doors and $M$ keys. Each door can be opened with a combination of keys, each combination is also unique (i.e. there aren't be two doors that are opened with same combination). 
For example, to open Door $1$ you need $3$ keys: $A, B$ and $C$. For Door $2$ you need $5$ keys: $C, F, G, E$ and $T$. All doors are accessible  (there are no doors behind a door).

Now the question is: can you chose $k$ keys, $k < M$, so that combination of keys lets you open the maximum number doors respect to any other combination of $k$ keys and, if the answer to this question is affirmative, which keys should be picked?

This kind of problem can't be solved by exhaustion since, in my case, there are $100$ keys and just generating all combinations would take centuries (there would be around $5.5\cdot 10^{20}$ combinations if $k=20$).

Im not too knowledgeable in algorithms, but this seems like some kind of constraint satisfaction problem but not exactly. Anyway I'm 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.

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.

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 3 keys: A, B and C. For Door 2 you need 5 keys: C, F, G, E and T. 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.