2

We have a problem we are trying to solve where we have a number of different containers. Each container can hold a number of different items (call them "item A" through to "item H"). Each container can handle a different ratio of the items before it is full. So taking just three of the containers the ratios the can handle may be:

Container 1 may be able to hold the items in the ratio like below:

A  B  C  D  E  F  G  H
1  2  3  3  3  3  2  1

Container 2 may be able to hold the items in the ratio like below:

A  B  C  D  E  F  G  H
1  2  3  4  4  3  2  1

Container 3 may be able to hold the items in the ratio like below:

A  B  C  D  E  F  G  H
1  1  2  2  3  3  4  4  

What we need to try and find out is how to best fit packs of items with smaller ratios with a maximum number of items (say 5 or 6) into the containers. We can find all the different permutations of packs using combinatorics. We have a limit that out of all of the pack ratio permutations we can only select 3 or 4 different ones to use, so have to discard the worst fits and keep the best 3 or 4.

What we are struggling with is a technique that can test for the best of the smaller packs into the larger containers that is both accurate and performant. Currently we have one or the other!

Any maths geniuses out there that can help?

  • I think this is a math problem, but could use some improvements in wording. I suspect the use of ratios will confuse or mislead many Readers. If the idea is that a single instance of Container N can hold an assortment of items given by integer counts, e.g. one of A, two of B, three of C, etc., and you want the smallest number of containers (or some other objective) needed to cover a given shipment, then you should probably ask at Math.SE with greater care about the details. – hardmath Sep 25 '15 at 11:12
3

This is a classic packing optimization problem and it belongs to the field of Computer Science, not Mathematics. The relevant literature is about algorithms for Packing Optimization or Container Optimization.

Take a look at the "Knapsack Problem" in wikipedia:

https://en.wikipedia.org/wiki/Knapsack_problem

Also, take a look at the "Bin Packing Problem" in wikipedia:

https://en.wikipedia.org/wiki/Bin_packing_problem

Related StackOveflow question about Bin Packing:

https://stackoverflow.com/questions/12056526/bin-packing-algorithm

  • 1
    Thank you. That has given me some good reading. I did not know the correct term to search! – Dib Sep 26 '15 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.