On 2007-04-12, Grant Edwards <[email protected]> wrote:
> I've been thinking more about the problem. I think with the
> degenerate case of only 2 bins, the problem isn't actually that
> hard. If I've got it figured correctly, doing it optimally is
> O(N^B), where N is the number of input sections and B is the
> numbr of bins. With N==2, a brute force optimal solution
> should be feasible (especially for a small number of input
> sections).
That can't be right. It's a combinatorial problem, so it has
to be O(N!). In any case, for large N the size of the chunks
that you're packing will be small, and any of the standard
non-combinatorial heuristic algorithms should work fine.
--
Grant Edwards grante Yow! Yes, Private
at DOBERMAN!!
visi.com
