Suppose that there are $M$ numbers, $a_1,\cdots,a_M$, and $K$ boxes. For each box $k$, $k=1,\cdots,K$, we can put $Q_k$ different numbers in it, in which each $Q_k$ is given and satisfies $1\leq Q_k < M$. Now I want to put different numbers into different boxes. Let $\mathcal{A}_m$ denote the set of boxes that has $a_m$, $m=1,\cdots,M$. Correspondingly, we can define $\mathcal{B}_k=\{m:k\in \mathcal{A}_m\}$ as the set of numbers that box $k$ has, $k=1,\cdots,K$.
There are many combinations to put different numbers into different boxes such that each number is in at least one box. But I want to find the best assignment strategy among all these combinations to solve the following problem
\begin{align} \mathop{ \underset{\mathcal{A}_1,\cdots,\mathcal{A}_M,P}{\min}} & ~ P \\ \mathrm{s.t.} \ \ \ \ & ~ \Lambda_m\neq \emptyset, ~~~ m=1,\cdots,M, \\ & ~ |\mathcal{B}_k| \leq Q_k, ~~~ k=1,\cdots,K, \\ & ~ \sum\limits_{k\notin \mathcal{A}_m}Q_k \leq P, ~~~ m=1,\cdots,M. \end{align}
In other words, if $a_m$ is not in box $k$, i.e., $k\notin \mathcal{A}_m$, we have a penalty of $Q_k$ for $a_m$, i.e., the capacity of box $k$. As a result, for any assignment strategy, the penalty for $a_m$ is $\sum_{k\notin \mathcal{A}_m}Q_k$, $m=1,\cdots,M$. We want to find one assignment strategy to minimize the maximum penalty among all the $M$ numbers.
In the special case of $Q_k=Q$, $\forall k$, i.e., all the boxes have the identical capacity, the optimal assignment is simple, because we can assign the numbers equally in different boxes with identical $|\mathcal{A}_m|$'s for all $m$. But I am not clear how to solve the above assignment problem in the general case with arbitrary values of $Q_k$'s.
Is there a closed form optimal value to the above problem, or is there any polynomial time algorithm to solve the above problem?
Thank you.
For each box $k$, we have a penalty of $Q_k$ for each $A_m$ not in box $k$. To minimize the penalty we need to put as many numbers as possible into each box. If we put $Q_k$ numbers in the box, there will be $M-Q_k$ numbers not in the box, and we have a penalty of $Q_k(M-Q_k)$. This is independent of which numbers are in the box.
Any distribution that has all boxes full will have minimum total penalty.