asked on

Algorithm Building and Rebuilding Pallets

I need an algorithm to build or rebuild pallets. It's pretty straight forward. 200 boxes per pallet, all boxes the same size. So, all I have to worry about is building as few pallets as possible.

An example:
Product #1, 100
Product #2, 73
Product #3, 48
etc.

They don't want products put on different pallets, so the 48 can't be split into 27 on one pallet and 21 on another. I was going to just sort by qty and keep adding until I can't add anything else to the pallet (in this case, pallet #1 would have 173 and #2 would have 48). This is an easy algorithm, but that won't build the most efficient pallets.

Any ideas?

Thanks!

Giuseppe Pizzuto

This is a so-called "knapsack problem 0-1".
What you described is a Greedy Algorhitm:
Take ever the maximum box available that fits the remaining space on the pallet.
This algorhitm is not the best, but is best "locally" (in each step takes the best choice)

If you want the best solution you have to use Dynamic Programming (DP) .

have a look at:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm

ASKER CERTIFIED SOLUTION

petr_hlucin

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

gebigler

ASKER

This will meet the need. Thanks!

Giuseppe Pizzuto

As you said,
This is an easy algorithm, but that won't build the most efficient pallets.

This because Greedy algorithm is optimal ONLY locally... and IS NOT the best solution !!!
Best wishes.