Re: set based guru's help wanted

Tech-Archive recommends: Speed Up your PC by fixing your registry

From: Steve Kass (skass_at_drew.edu)
Date: 12/12/04 

Date: Sat, 11 Dec 2004 22:54:35 -0500

This is not an NP-complete bin packing problem, as I understand it.
It's a very simply "box-filling" problem in which the greedy algorithm
guarantees an O(N) solution, at least two of which have already been
posted in this thread.

Did you bother to read any of this thread carefully? It's really no
help to mislabel a problem that has already been answered and then refer
to a book you can neither name nor find nor quote from.

SK

--CELKO-- wrote:

>You are in trouble; this is an NP complete bin packing problem. Two
>Italtians did a book on this topic years ago, with FORTRAN programs
>and it might be help. I cannot find my copy.
>
>If you can just stuff students into rooms without any constraints about
>trying to preserve blocks, then the easy way is probably a greedy
>algorithm with cursors that set up a queue of classes and a queue of
>rooms. The matching is pretty straight forward: sort and pair up.
>
>aaaa abb bbc cccd ddd
>1111 222 333 4444 555
>
>but it is not optimal in the sense of the fewest mixed rooms. (3 versus
>1)
>
>aaaa bbb ccc dddd abc
>1111 222 333 4444 555
>There are about 8 ways to define "optimal" or "near-optimal"
>
>
>