Constructing an optimal solution to bin packing using a "magical function" $\phi$

Question

I am taking an introductory course in complexity theory, and as an exercise, we were given the following problem.

Consider the bin packing problem, with objects of positive (rational) weights $W = \{w_1, w_2, ..., w_n\}$ ($0 < w_i \leq 1 \forall i$) that should be placed in bins of capacity 1. Imagine that you are given a "magical function" $\phi$ that, given a set $W$ of weights, gives you the minimum number $k$ of bins needed to pack the corresponding objects, i.e., $\phi(W) = k$. Let $T(n)$ denote the running time of the implementation of $\phi(W)$ and construct an algorithm that returns an optimal packing and runs in $O(f(n) + g(n)T(n))$ time, where $f(n)$ and $g(n)$ are polynomials.

First, I tried to recursively make binary partitions of $W$ by using that $\phi(W_1) + \phi(W_2) = \phi(W)$ for any partition $W_1 \cup W_2 = W$ such that $W_1$ and $W_2$ separates objects that are in different bins in an optimal solution (that is, there is an optimal solution such that no weights in $W_1$ share bins with any weight in $W_2$). When we eventually get $\phi(W_j) = 1$, we know that $W_j$ corresponds to the objects in bin $j$ in an optimal solution. However, my attempts here only yield algorithms with $g(n)$ being exponential in $n$.

Second, I tried to construct the bins one by one, using that, for all bins $B_j$, $\phi(B_j) + \phi(W \setminus B_j) = k$. Again, I have yet to find an algorithm where $g(n)$ is polynomial.

It's rather frustrating, as this seems to be a simple problem. Any suggestions on where I should begin?

Answer 1

Starting with $W$, repeatedly try to find two weights $w_i,w_j$ such that merging them (i.e., replacing both of them with $w_i+w_j$) doesn't increase the number of bins needed. Eventually, you will be left with $\phi(W)$ merged weights, which form a solution to the bin packing problem.