Return to Revisions

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.