Vartiation of the knapsack

Question

Your job is to pack n objects in boxes. Each box can have one or two items, and the total weight of items in the box can be at maximum x. What is the minimum number of boxes?

I cannot figure out if the problem here is the Knapsack or something else...

For the regular Knapsack I have

def knapsack(x, wt, values, n):
    if n == 0 or x == 0 : 
        return 0
    if (wt[n-1] > x): 
        return knapsack(x, wt, values, n-1)  
    else: 
        return max(val[n-1] + knapsack(x-wt[n-1], wt, val, n-1), knapsack(x, wt, val, n-1))

but I'm not sure how to modify this? Also, it seems that I'm looking for the minimum here instead of the maximum. Could this also be some variation of the subset-sum?

Answer 1

You don't need to go knapsack here since all the items must be packed. You also don't need to use bin packing since your boxes are limited to either 1 or 2 objects. A greedy algorithm is much simpler. Take the following:

1. Sort the objects from heaviest to lightest
2. Take the heaviest object to be H and the lightest object to be L. If H + L > x, then there is no other object H can be packed with and it must be packed by itself. Otherwise packing H and L together minimizes the boxes since putting L with any other object would not further minimize the number of boxes (as a proof, see that if some other object can be packed with L but not any other object, then H also cannot be packed with that other object).
3. Repeat until all objects are packed

This is an O(nlog(n)) solution which is made possible by the limit on the number of items per box. If there was no limit on the number of items, then you would have to resort to bin packing.