# Is this variant of multiset covering problem NP-hard?

Consider this variant of multiset covering problem.

Input: a collection of sets $$S = \{s_1, s_2, \ldots, s_n\}$$ and a universal set $$U$$, in which $$s_k \subseteq U$$ and $$s_k \neq \emptyset$$ for all $$k$$.

The problem is, given an non-empty multiset $$M$$ containing elements from $$U$$, we are allowed to pick at most one element from each set in $$S$$ to form a new multiset $$P$$. We need $$P$$ to cover $$M$$ as many times as possible. For $$P$$ to cover $$M$$ $$n$$ times means for each element in $$M$$, there are at least $$n$$ copies in $$P$$.

For example, if $$S = \{\{1, 2, 3\}, \{2, 3\}, \{2\}, \{2\}, \{1\}, \{1\}, \{1, 3\}\}$$ and $$M = \{1, 1, 2\}$$, we should be able to form $$P = \{1, 2, 2, 1, 1, 1\}$$ by picking 1 element from the 1st, 2nd, 3rd, 5th, 6th and 7th sets respectively. This will cover $$M$$ 2 times. (To cover $$M$$ 3 times will require six $$1$$s and three $$2$$s, which is impossible from just 7 sets)

Is the above problem NP-Hard?

Make a bipartite graph where one side is $$S$$, and the other side is $$B$$, made up of $$n$$ copies of $$M$$. If you enumerate the elements of $$M$$, $$m_1,\ldots,m_k$$, then $$b_{i,j}\in B = m_j$$ for all $$i\in [n]$$. Then draw an edge from $$s_\ell$$ to $$b_{i,j}$$ iff $$m_j\in s_\ell$$ for all $$i,j,\ell$$. Now it's easy to see that you can cover $$M$$ $$n$$ times iff there is a matching in the graph with $$|B|$$ edges. Trying with different sizes of $$n$$, you can find the greatest one.
There is probably a more efficient way to find a matching that saturates one side $$n$$ times (such that you only need one copy of $$M$$), but this at least shows that the problem is not NP-hard (unless P=NP, of course).