Suppose we have $N$ items, say $N=300$. We know that $N$ is divisible by $p$.
We then have $k$ demands, each of size $d[k]$. For example, $(125,125,50)$ where $k=3$ and $d[k]=125, 125, 50$ for $k=1,2,3$.
Note that $d[k]$ need not be integer-valued, but we can assume it sums to $N$.
Question, how do I split $N$ into $k$ parts, so that all $d[k]$'s are matched as close as possible, with the following conditions:
- we must allocate all $N$ (and $N$ exactly).
- the split must be a multiple of $p$. So say, $p=3$, then all $d[k]$ must be a multiple of 3.
Note, the split can be greater than the demand. For example allocating $126$ to a demand of $125$ is ok.
A case study:
$N=300, p=3, d[k]=(125,125,50)$.
A possible solution might be $(123,126,51)$. All demands are divisible by $3$. They add up to $300$, and they are close to $(125,125,50)$.
Mathematically, it is
given $d[i]_{i=1,2,...,k}, p$, and $N$,
$min_{x[i]} \sum_i^k |d[i]-x[i]|$
such that
$x[i]$ is integer and divides $p$ for all $i$, and
$\sum_i x[i]=N$.
Is there a name for this problem? I suppose we can solve it via integer programming, but is there a specialised routine to do this?