## 07 December 2008

### Problem from a program verifier

Problem. You are given the positive weights w1,…, wn and a limit W. Partition them using as few subsets of weight ≤ W as possible.

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

Cosmin said...

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.

rgrig said...

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.

rgrig said...

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?

Jim Apple said...
rgrig said...

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.

rgrig said...