# N songs, M instruments, how to pick K instruments to cover maximal amount of songs

I have $N$ songs, $M$ instruments.

Each song requires one or more of the $M$ instruments in order to be played.

My $K-1$ friends and I want to learn to play $K$ different instruments, and we want to pick them such that we maximize the amount of songs we will can play.

How would I efficiently solve this? I'm sure this problem maps to some well known computational problem, but nothing comes to mind at the moment.

• I don't understand your question. Suppose that some song requires drums, bass guitar and electric guitar. Even if you learn all three of those instruments, you're not going to be able to play the song, unless you have more arms than I do. – David Richerby Oct 7 '16 at 14:22
• ;) This isn't really about me learning instruments. I do need to select K instruments that include the maximal amount of songs though. N and M are large enough that brute force seems unworkable. – larspars Oct 7 '16 at 14:37
• This is unsolvable due to inefficient data. Even if weak, a Song - Instrument correlation has to be provided. – Redu Oct 7 '16 at 21:59
• You can assume that a list of what instruments are required for each song is provided as input. – larspars Oct 7 '16 at 22:22

I don't know a canonical name for this problem, but unfortunately it's NP-hard, even when every song requires at most 2 instruments. The upshot is that it's extremely unlikely that any polynomial-time algorithm exists that will solve every instance of your problem. I'll show this by reduction from the NP-hard problem Maximum Clique, in which we are given an undirected graph $G = (V, E)$ and a positive integer $k$, and asked whether there exists a clique of size $k$ in the graph.
To construct an instance of your problem from the Maximum Clique Instance: Create a song $s_{uv}$ for every edge $(u, v)$ in $E$, and an instrument $t_v$ for every vertex $v$ in $V$, and make song $s_{uv}$ require the two instruments $t_u$ and $t_v$. Set $K$ (part of the input to your problem) equal to $k$ (part of the input to the Maximum Clique problem). Now run any algorithm that solves your problem on the just-created instance: if the answer is $\ge k(k-1)/2$ then return YES, otherwise return NO. (Clearly this procedure could work just as easily with an algorithm that solves the "pure decision" form of your problem, i.e., when a number $r$ is also given as part of the input, and the task is to determine whether it is possible to choose at most $K$ instruments such that at least $r$ songs can be played.)
It is easy to see that, if $G$ contains a clique of size at least $k$, then we must correctly get a YES answer: by assumption, there is a $k$-vertex clique, which comprises $k(k-1)/2$ vertex pairs, each of which are connected by an edge, so choosing the corresponding $k$ instruments satisfies the $k(k-1)/2$ corresponding songs.
In the other direction, suppose that the algorithm for your problem reports that at least $k(k-1)/2$ songs can be played; we need to show that this implies that there is a $k$-clique in $G$. Given that we permitted at most $k$ instruments to be chosen, there certainly cannot be more than $k(k-1)/2$ songs that we can play, since every song requires a distinct pair of instruments: so we can infer that exactly $k(k-1)/2$ songs can be played. But every choice of at most $k$ instruments that does not correspond to a $k$-clique in $G$ omits at least one of these $k(k-1)/2$ edges, and thus allows strictly fewer than this maximum possible number of songs to be played; thus the only subgraphs on at most $k$ vertices that can result in at least $k(k-1)/2$ edges are subgraphs that are $k$-cliques.