I have a large matrix that is populated with a list of people, and a 1 or 0 as to whether or not they have a particular flag. A person can have one or more flags, or none at all. For example:
$ \begin{matrix} Person & Flag1 & Flag2 & Flag3 \\ John & 1 & 0 & 0\\ Mary & 1 & 0 & 1\\ Luke & 0 & 1 & 0\\ Paul & 0 & 0 & 0\\ \end{matrix} $
I can clear only one flag at a time (i.e. set a column to 0 for the whole population), and each requires about the same amount of work. My goal is to clean (a clean person has no flags) a certain percentage, p, of the population. How can I (besides trial and error) figure out the most efficient flag clearing strategy?
EDIT: My second thought to this was to think of the problem from the opposite side, or "how many flags can I keep and still maintain a p clean percentage". For this, I'd iterate through combinations of the columns, and see which combinations left me with clean / total >= p, and choosing the combination with the largest amount of columns.
EDIT: Can someone prove that there is an efficient solution? My gut tells me it could definitely be np-hard but I can't find a way to prove either a reduction or a poly-time algorithm.