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}