Let's say we have a set U = {x1, x2, x3} and a set S = {{x1},{x1, x2},{x1, x3},{x1,x1,x3}}. This is purely an example and the problem is for the general problem. This looks just like a regular set cover problem, which is why I figure reducing it to a true set cover problem is feasible. The twist is that the elements in U needs to be 'picked' z amount of times, where z is different for each x1, x2, x3.... and so forth.
Any subset in S can only pick up the elements they have inside them ONCE. Given a number 'k', is it possible to form a collection of subsets in S so that
- Every element in U is included.
- Every element is included z amount of times, where z is different for all x'es.
If i can formulate the Set Cover problem in such a way that'd be great, but im stuck at this part.
The covering problem is NP-complete, because of it, heuristic methods are employed to found good solutions."The algorithm design Manual" from Skiena have a detailed discussion about the subject.