Cover the set with another set, so that elements got separated as little as possible.

33 Views Asked by At

Let us suppose I have a set which consists of positive numbers $P=\{p_1, ..., p_n\}$ and I have another set which consists of positive numbers $Q=\{q_1, ..., q_m\}$. I know that $p_1+ ...+ p_n=q_1+ ...+ q_m$. I need to cover the set $Q$ with the help of the set $P$, so that every number in $Q$ got covered. To cover a number $q$ in the $Q$ means to map it to numbers $p_{k1}, ..., p_{kj}$ (where $_{kj}$ is from $_{\{1, ..., n\}}$) in $P$ so that the sum of those numbers would be equal or greater than $q$.

For example, $P=\{1, 2, 3, 7\}$ and $Q = \{6, 6, 1\}$, then one of the possible coverages would be as follows: $1+2+3=6$, $7=6+1$ and $1=1$ (since after $7=6+1$ we a left with $1$ from $7$).

How could I design such a coverage, so that there would be as little remainings as possible?

For example, in the map above there is only $1$ remaining - it is $1$ after the $7$ covered $6$.

Here is my thoughts about how I could do that, but I am not sure whether or not I am correct.

  1. Sort $Q$ in the ascending order. Take every element from the sorted $Q$ in ascending order and map it to elements in the $P$. At every mapping step choose from the appropriate subsets of the $P$ the subset with the biggest cardinality.

  2. Now find every remaining and try to get rid of it.