Problem. You are given the positive weights w1,…, wn
and a limit W. Partition them using as few subsets of weight ≤ W
Question. I know a solution that takes Θ(3n) time.
Can you do better? Can you find a lower bound?
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-packingReduction 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!
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.