Weekend Programming Challenge – Week #51 – container load


Image

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.

9 Comments (+add yours?)

  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)

    Reply

    • OLIMEX Ltd
      Apr 26, 2014 @ 14:46:41

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

      Reply

      • 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”.

  2. Dylan
    Apr 27, 2014 @ 20:42:37

    Reply

  3. dennis Restle
    Apr 30, 2014 @ 12:58:06

    do the containers have to lay on their Ground or can in turn/rotate left/right/up/down them like i whish?

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 572 other followers

%d bloggers like this: