I have the following definition of a BinPack problem:
The problem is to place a certain number of objects in a certain number of bins. The objects have different weights, each bin accepting a maximum load (all bins can accommodate the same load here). The associated BinPack property is formally defined as follows:
Input:
- n: number of objects
- x1, ..., xn: n integers, the weights of the objects
- c: bin capacity (integer)
- k: number of bins
Output:
- Yes, if there is a possible packing.
- No, otherwise.
The following definition of a decision problem associated with the BinPack problem is also provided: Let this problem be called BinPackOpt
Input:
- n: number of objects
- x1, ..., xn: n integers, the weights of the objects
- c: bin capacity (integer)
- k: number of bins
Output: A correct packing that minimizes number of bins.
I need to show that if the BinPack problem was in P, then BinPackOpt would also be in P.
Therefore, I must construct a packing in polynomial time using the polynomial time algorithm of the BinPack problem. I already figured out how to get the minimum number of bins in polynomial time by using a binary search algorithm with bounds 1 and n initially and fixing the bounds according to outcome of the BinPack problem. That is, if we can accommodate the objects in "median" number of bins, then I fix the upper boundary to median, and if not, I fix the lower boundary to median + 1 which gives me an algorithm in O(P(n).log(n)) where P(n) is the complexity of the BinPack problem. However, I am not able to figure out how to get the actual packing of the objects in this optimal number of bins in polynomial time.
How can I solve this issue? Any help is appreciated.
You can find the fewest number of bins necessary for BinPackOpt to find any packing, as you say, via a binary search in which BinPack will be called O(log n) times.
Let's say the minimum number of bins necessary for a packing to be possible is found to be k. Then the following pseudocode will give you the optimal packing:
let current_set = {obj_1, ..., obj_n}
loop1: let test_obj be the first object in current_set
loop2: for each obj_i in current_set not equal to test_obj
let test_set = current_set - {test_obj, obj_i}
add a new object to test_set that has the combined weight of test_obj and obj_i
call BinPack on test_set with k bins of the given capacity
if BinPack succeeds
record that test_obj and obj_i are binned together
let current_set = test_set
goto loop1
record that test_obj is binned alone
let test_obj = test_obj+1
goto loop2
The inner loop of the above places one object into a bin of the optimal packing using O(n) calls to BinPack so you can find the whole optimal packing with O(n^2) calls to BinPack.