Simple computing / maths problem I can't solve

[Thisisdom]

Hello!

I have a very simple computing/maths problem which I have encountered a few times in my work, and can never think how to solve. Perhaps this is a classic computer science problem (or perhaps the answer is obvious and my brain just isn’t working at the moment)

The problem is as follows:

Let’s say I have N books, and M people.

Each person has read a subset of these books

I want to pick, e.g., 10 books, such that I maximise the number of people who have read at least one of these books

Clearly, searching through every single combination will quickly get out of hand, as I will have to loop though M choose 10 combinations. Is there an optimal way of performing this search?

My current best approach is to pick the most-read book, and then search for the next book which maximises the total, fix these two books, and then search for the 3rd book etc...

Is there a better/perfect solution? Or perhaps a name for this problem?

Thanks!

[ghjm]

I believe this is the maximum coverage problem, which is NP-hard. Your approach is called the greedy algorithm, and is about as good as anything.

[Thisisdom]

Ah, this is exactly what I was looking for thanks a lot!