# Filling up a bin using balls with divisible weights

This post shows how to solve the special case for this problem. The special case has exactly one bin, and each ball have weight a power of $2$. It is one of the most popular unanswered problem on cs.stackexchange as of writing.

We are interested in solving the following integer program, $Minimize:subject to: i=1∑n ∣x_{i}−a_{i}∣i=1∑n w_{i}x_{i}=c0≤x_{i}≤b_{i}for all1≤i≤n. $ where each $w_{i}$ is a power of $2$ for all $1≤i≤n$. Assume $w_{i}≤w_{i+1}$.

In fact, we do not require the $w_{i}$s are powers of $2$. We can establish polynomial time as long as $w_{i+1}/w_{i}$ is bounded by a polynomial in terms of the input size for all $i$. However, for simplicity of exposition, assume $w_{i}$s are powers of $2$. We do not know the case when $w_{i+1}/w_{i}$ is unbounded.

Consider a more natural problem without the absolute values.

We are interested in solving the following integer program, $Minimize:subject to: i=1∑n c_{i}x_{i}i=1∑n w_{i}x_{i}=tx_{i}∈{0,1}for all1≤i≤n $

where $w_{i}∣w_{i+1}$ for all $1≤i≤n$. $w_{i}$ can be negative.

We show Problem 1 reduces to Problem 2 with polynomial blow up, and Problem 2 can be solved in polynomial time.

# 1 Reduction

The reduction goes through a few steps. We start with the integer program in [Problem 1], and let $y_{i}=a_{i}−x_{i}$, and we get

$Minimize:subject to: i=1∑n ∣y_{i}∣i=1∑n w_{i}y_{i}=i=1∑n w_{i}a_{i}−ca_{i}−b_{i}≤y_{i}≤a_{i}for all1≤i≤n $

Let $c_{′}=∑_{i=1}w_{i}a_{i}−c$, and $l_{i}=a_{i}−b_{i}$ and $u_{i}=a_{i}$.

$Minimize:subject to: i=1∑n ∣y_{i}∣i=1∑n w_{i}y_{i}=c_{′}l_{i}≤y_{i}≤u_{i}for all1≤i≤n $

Let $y_{i}=y_{i}−y_{i}$, where $y_{i},y_{i}≥0$, we can remove the absolute value.

$Minimize:subject to: i=1∑n y_{i}+y_{i}i=1∑n w_{i}y_{i}+i=1∑n −w_{i}y_{i}=c_{′}l_{i}≤y_{i}−y_{i}≤u_{i}for all1≤i≤ny_{i},y_{i}≥0for all1≤i≤n $

Observe that we can separate the inequalities involving $y_{i}−y_{i}$, because there is always an optimal where $y_{i}$ or $y_{i}$ is $0$.

This observation fails when the number of bins is more than $1$.

$Minimize:subject to: i=1∑n y_{i}+y_{i}i=1∑n w_{i}y_{i}+i=1∑n −w_{i}y_{i}=c_{′}0≤y_{i}≤u_{i}for all1≤i≤n0≤y_{i}≤−l_{i}for all1≤i≤n $

This is an integer program as a bounded exact knapsack problem.

$Minimize:subject to: i=1∑n x_{i}i=1∑n w_{i}x_{i}=c0≤x_{i}≤b_{i}for all1≤i≤n $

Finally, apply the standard technique that rewrites a bounded knapsack problem to $0$-$1$-knapsack problem (see Section 7.1.1 of [1]). The blow up in problem size is at most a factor of $O(gmax_{i}b_{i})$. We can get the integer program in Problem 2, and also the weights are all powers of $2$. The reduction runs in polynomial time with respect to input size.

# 2 Solving Problem 2

Yuzhou Gu noted that the integer program in Problem 2 has a dynamic programming solution.

Let $D[m,k]$ to be the optimal value to the following problem

$Minimize:subject to: j=1∑m c_{j}x_{j}j=1∑m w_{j}x_{j}=k∣w_{m}∣+tmod∣w_{m}∣x_{j}∈{0,1}for all1≤j≤m $

The claim is that $D[m,k]$ can be expressed by the following recurrence relation.

$D[m,k]=x_{m}∈{0,1}min D[m−1,∣w_{m−1}∣∣w_{m}∣k−w_{m}x_{m}+(tmod∣w_{m}∣−tmod∣w_{m−1}∣) ]$

Note that $∣k∣$ is at most $m$. Therefore the table has at most $O(n_{2})$ entries. To obtain the solution to the original equation, we find the minimum overall $D[n,k]$. Clearly, this runs in polynomial time.

# References

[1] H. Kellerer, U. Pferschy, D. Pisinger, **Knapsack problems**, Springer, 2004.