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.



Im looking for an algorithm that can solve or approximate the solution to a problem
You can solve this problem via integer linear programming. Let binary decision variable $x\_i$ indicate whether you can open door $i$, and let binary decision variable $y\_j$ indicate whether you select key $j$. The problem is to maximize $\sum\_{i=1}^N x\_i$ subject to
\begin{align}
\sum\_{j=1}^M y\_j &= k \\
x\_i &\le y\_j &&\text{if door $i$ requires key $j$}\\
x\_i &\in \{0,1\} &&\text{for $i\in\{1,\dots,N\}$}\\
y\_j &\in \{0,1\} &&\text{for $j\in\{1,\dots,M\}$}
\end{align}
By request, here's the SAS code (with more descriptive variable names than x and y) that I used to solve the sample instance:



```
proc optmodel;
   /* declare parameters and read data */
   set <str> RECIPES;
   read data lib.doors into RECIPES=[var1];
   num numIngredients_r {r in RECIPES} = countw(r,',;');
   set INGREDIENTS_r {r in RECIPES} = setof {k in 1..numIngredients_r[r]} scan(r,k,',;');
   set INGREDIENTS = union {r in RECIPES} INGREDIENTS_r[r];

   /* declare decision variables */
   var UseIngredient {INGREDIENTS} binary;
   var SelectRecipe {RECIPES} binary;

   /* declare objective */
   max NumSelectedRecipes = sum {r in RECIPES} SelectRecipe[r];

   /* declare constraints */
   con Cardinality:
      sum {i in INGREDIENTS} UseIngredient[i] = 200;
   con RecipeImpliesIngredient {r in RECIPES, i in INGREDIENTS_r[r]}:
      SelectRecipe[r] <= UseIngredient[i];

   /* call MILP solver */
   solve;

   /* output solution */
   create data SolutionIngredients from [i]={i in INGREDIENTS: UseIngredient[i].sol > 0.5};
   create data SolutionRecipes from [r]={r in RECIPES: SelectRecipe[r].sol > 0.5};
quit;

```

Note that the UNION set operator avoids reading a separate ingredients file, and so I did not need to exclude any data. The resulting optimal solution for 200 ingredients yields 1345 recipes.


