This is a real life question.. I have a list of N favorite songs from an artist. Out of all M albums from the artist ever published,I want to buy a few albums to cover all of my N favorite songs, but I also want to minimize my spending. How to set up this problem as an optimization problem and how to solve it?
I feel this is an binary optimization program, as I either buy an album or not buy it.
This problem is called integer programming. You could formalize it as follows:
$\min_{w} C(w) = \min_w \sum_{m=1}^Mw_mc_m,$
where $c_m$ is the cost of album $m$ and $w_m\in\lbrace 0;1 \rbrace$ indicates if you buy album $m$. Note that minimizing the total cost $\min C(w)$ is equivalent to $\max -C(w)$. The objective is subject to the following restraints:
$n=1,\ldots,N:\ 1 \leq \sum_{m=1}^M w_m \mathbf{I}_{m,n}$
where $\mathbf{I}_{m,n}$ is $1$ if album $m$ contains song $n$.
Now you would need to put the constraints into matrix form $\mathbf{I}$ (by filling the matrix appropriatly with zeros and ones, rows corresponding to songs and columns to songs).
E.g., you can solve the problem in R with the package lpSolve.
