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!
gebiglerAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

gpizzutoCommented:
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
0
petr_hlucinCommented:
This problem is NP-hard which (explained in a simple way) means that we don't know about polynomial algorithm which solves this problem. If you needed the most optimal solution the algorithm would be probably O(m^n) where m is pallettes count and n is boxes set count.

However an approximative solution would be like this:
sort sets of goods according to the size
while sets of goods are remaining do
  while largest set fits onto the current pallette
    put the largest set on the current pallette
  end while
  while smallest set fits onto the current pallette
    put the largest set from the remaining sets on the current pallette
  end while
  ship pallette
end while

For the test data the algorithm would work like this:
- put 100
- put 48
- ship pallette with 148
- put 73
- whip pallette with 73
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
gebiglerAuthor Commented:
This will meet the need.  Thanks!
0
gpizzutoCommented:
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.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.