You can seach google for "packing algorithm" and discover:
http://www.astrokettle.com/data.html http://en.wikipedia.org/wiki/Bin_packing_problem
Your problem can be mapped to the "stock cutting problem", so you should do
a search for those algorithms too.
If you can constrain the ways in which you can fill a carton,
here is a rather naive approach that should be within 22% of optimal:
(see
http://mathworld.wolfram.com/Bin-PackingProblem.html)
1. Order the cartons smallest to largest.
2. Order the items largest to smallest.
Foreach item:
select the first carton/subcarton that the item will fit in.
reduce the subcarton by dividing it into the subcartons that are left.
A "subcarton" is a cuboid (solid having 6 rectangular faces) that represents
some of the volume of the carton. The first time you add an item to a
carton you have left a set of cuboids (representing the volume left in the
carton). When you add an item to a cuboid, you dissect that cuboid into the
ones that remain, etc. So, the algorithm above looks at the subcartons
within the carton in attempting to fit the next item into the carton.
Note that when you add the first item to a carton, you can dissect the
remaining volume into 2 cuboids, in 2 different ways (and that is true for
each way you can place the item into the cuboid). If your items only fit one
way into the carton (as in your example) it will fit only one way into a
cuboid; you can see that this simplifies the problem considerably.
However, if there is more than one way to disect the remaining volume into
cuboids, you might want to do a depth-first search on the possibilities, or
some other optimization technique.
http://www.frontiernet.net/~fredm/dps/Contents.htm might be of use in that
case.
"sklett" <s@s.comwrote in message
news:%2******** ********@TK2MSF TNGP06.phx.gbl. ..
>I realize this could be a little off-topic, but there are some great minds
on this NG and I hope you can let me slide this time ;0)
I'm designing our system to manage what products can fit in which cartons
and how many per carton. For example:
Widget A measures 10W x 10H x 10D
Carton A measures 20W x 10H x 10D
Carton B measures 50W x 10H x 10D
If I'm fulfilling an order for 2 Widget As I can choose Carton A as it
will contain 2 Widget A items.
Order for 50, Carton B, etc.
I would like to design a system that will eliminate user interaction in
this area, I would like my system to asses the item dimensions and
quantity and choose the appropriate carton.
The ideas that are floating through my head to solve this are far too
basic to be efficient and would result in a mess a spaghetti code handling
orientation combinations, etc.
Does anyone know of an algorithm that is designed to solve this problem?
I'm sure there is something out there, but my initial googling hasn't come
up with anything valid.
I hope you understand what I'm trying to achieve.
I appreciate any help!
Thanks,
Steve
