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 . It is one of the most popular unanswered problem on cs.stackexchange as of writing.
We are interested in solving the following integer program, where each is a power of for all . Assume .
In fact, we do not require the s are powers of . We can establish polynomial time as long as is bounded by a polynomial in terms of the input size for all . However, for simplicity of exposition, assume s are powers of . We do not know the case when is unbounded.
Consider a more natural problem without the absolute values.
We are interested in solving the following integer program,
where for all . can be negative.
The reduction goes through a few steps. We start with the integer program in [Problem 1], and let , and we get
Let , and and .
Let , where , we can remove the absolute value.
Observe that we can separate the inequalities involving , because there is always an optimal where or is .
This observation fails when the number of bins is more than .
This is an integer program as a bounded exact knapsack problem.
Finally, apply the standard technique that rewrites a bounded knapsack problem to --knapsack problem (see Section 7.1.1 of ). The blow up in problem size is at most a factor of . We can get the integer program in Problem 2, and also the weights are all powers of . The reduction runs in polynomial time with respect to input size.
2 Solving Problem 2
Let to be the optimal value to the following problem
The claim is that can be expressed by the following recurrence relation.
Note that is at most . Therefore the table has at most entries. To obtain the solution to the original equation, we find the minimum overall . Clearly, this runs in polynomial time.
 H. Kellerer, U. Pferschy, D. Pisinger, Knapsack problems, Springer, 2004.