Problem:

Freight company have N parcels with different dimensions to fit in 20 feet containers. Make code which optimally fill containers inside volume. Assume that there is no limitations to stack the parcels.

The rules:

You can code the solution in any programming language during the weekend and have to submit it to info@olimex.com latest on Sunday April 27th.

On Monday we will upload the solutions on GitHub https://github.com/OLIMEX/WPC

You can play with your real name or with nick if you want to be anonymous, we will not disclosure your personal info if you do not want to.

1. Anonymous
Apr 26, 2014 @ 03:01:46

And don’t forget to apply for the Fields Medal if you find an algorithm that gives optimal solutions.

In the meantime you may try finding the answer to the much easier – but still unsolved – problem: What’s the smallest square the can hold eleven 1×1 squares? (non-overlapping, of course)

• there are some algorithms which will give near optimal solution in most of the cases without brute force

• Anonymous
Apr 27, 2014 @ 16:45:37

Hmm… I would like to see that 😉

I guess, you wanted to give an example for the “bin packing problem” where there are “good enough” algorithms. That would work if you’d used the weights of the parcels and the maximum weight a container may hold. Here the decision “does this parcel still fits into this container” is easy, simple weight comparison.

But you’d given the size of the parcels and a container size. By that you combine the “bin packing problem” with a generalized form (arbitrary box sizes, 3D) of the “square packing in a square” problem. The “does it fit” question becomes really hard now. “Brute force” – which requires a finite number of posibilities – no longer applies as there’s an infinite number of ways to place parcels into a container.

For anybody playing around with this problem, here’s test set of parcels: one big 8x8x19 parcel and five small 2.9×2.9×1 parcels. One container or two? A human would most probably have no problem packing them in one 🙂

But maybe I’m totally wrong. I’m by no means an expert in this field and there may already be some nice algorithms to solve the “does it fit” problem (if you know, some URLs would be nice). I just like these kind of “mind games”.