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?

8 comments:

Anonymous 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".

Unknown said...

And what was your O(3^n) solution?

Jim Apple said...

Reduction from partition to bin-packing

Reduction from subset-sum to partition

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...

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

rgrig said...

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.