Logic Issue - how many / which small boxes in a big box - PHP/MySQL

Question

I've got a problem, and I'll try and describe it in as simplest terms as possible.

Using a combination of PHP and MySQL I need to fulfil the following logic problem, this is a simplified version of what is required, but in a nutshell, the logic is the same.

Think boxes. I have lots of small boxes, and one big box. I need to be able to fill the large box using lots of little boxes.

So lets break this down.

I have a table in MySQL which has the following rows

Table: small_boxes
id | box_size
=============
1  | 100
2  | 150
3  | 200
4  | 1000
5  | 75
..etc

This table can run up to the hundreds, with some boxes being the same size

I now have a requirement to fill one big box, as an example, of size 800, with all the combinations of small_boxes as I find in the table. The big box can be any size that the user wishes to fill.

The goal here is not efficiency, for example, I don't really care about going slightly under, or slightly over, just showing the different variations of boxes that can possibly fit, within a tolerance figure.

So if possible, I'd like to understand how to tackle this problem in PHP/MySQL. I'm quite competent at both, but the problem lies in how I approach this.

Examples would be fantastic, but I'd happily settle for a little info to get me started.

Answer 1

You should probably look into the glorious Knapsack problem