**Problem.** You are given the positive weights *w*_{1},…, *w*_{n}
and a limit *W*. Partition them using as few subsets of weight ≤ *W*
as possible.

**Question.** I know a solution that takes Θ(3^{n}) time.
Can you do better? Can you find a lower bound?

## 8 comments:

Isn't this a generalization of the knapsack problem? I wish you good luck in trying to solve it optimally :) you might get the million dollars on the line.

Yes, it looks a lot like knapsack, but somehow I didn't figure out how to transform an instance of knapsack (or subset sum) into an instance of this.

Cosmin showed me a

O(n 2^n)solution: put one weight at a time in the last subset as long as it fits, try all possibilities for the "next weight". So 2^n comes from "all subsets of covered weights" and n comes from "all possibilities for adding the next weight".And what was your O(3^n) solution?

Reduction from partition to bin-packing

Reduction from subset-sum to partition

Say cover(A) is the minimum number of subsets you need. Then:

cover(A)=min(1 + cover(B))

You iterate over all B included in A and filter out if A-B is not valid (too heavy). The valid subsets are precomputed.

@Jim Apple: Thanks for the links. I'll read those.

OK, so this is exactly the bin packing problem. Thank you!

## Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.