[comp.theory] Bin Packing

rjf@eecg.toronto.edu (Bob Francis) (04/19/91)

Subject: Bin packing

I am looking for information on bin packing algorithms
that deal with integer sized bins and boxes.

ie.
	Given an integer K, a finite set of boxes

		U = {u_1, u_2, ... u_n}

	and an integer size, s (u_i), 
	between 1 and K for each box u_i in U.

	Parition U into disjoint subsets

		U_1, U_2, ... U_m

	such that the sum of the sizes of the boxes 
	in any subset U_i is less than or equal to K
	and such that m is as small as possible.


In pariticular, I would like to know if dynamic programming
has been applied to this problem.

Please reply by e-mail.

	Bob Francis
	rjf@eecg.toronto.edu