# Thread: Fitting Blocks into Boxes Problem

1. ## Fitting Blocks into Boxes Problem

I have a problem that I need to make a computer algorithm to solve. I thought someone here might be able to give me some ideas.
The basic problem is this:
There are 3 children each with their own box.

-George's box is 20 inches tall.
-Thomas' box is 8 inches tall.
-Abe's box is 7 inches tall.

In the room there is an assortment of blocks. The blocks have different heights. We must find a way for the children to be given various blocks so that the sum of the block heights they each are given is not higher than each children's box.

The blocks in the room and their heights are as follows:
- There is one block that is 2 inches tall.
- There is one block that is 3 inches tall.
- There are 6 blocks that are 5 inches tall.

How do you write an algorithm to perfectly distribute the blocks so each child's box does not overflow?

The answer to this is pretty easy.
- George: 4 of the 5 inch blocks. Total is 20 inches.
- Thomas: 1 of the 5 inch blocks and the 3 inch block. Total is 8 inches.
- Abe: 1 of the 5 inch blocks and the 2 inch block. Total is 7 inches.

But if I had written a computer program to distribute the blocks in the order in which I listed them, it would not have worked. George would get both the 2 inch and 3 inch block, then 3 of the 5 inch blocks. There would be 3 of the 5 inch blocks left over and both Thomas and Abe can only accept one of them. Leaving one left over that no one can accept.

The only way I can think is to write a program that loops through every combination until something works. Is there a way that takes less computing resources?

Furthermore, after I solve this, I am going to need to make the program work with any assortment of blocks, sizes, and children. So I am really looking for an approach to solving this and not simply a way to solve this one example.

2. ## Re: Fitting Blocks into Boxes Problem

Try distributing the blocks in reverse order of size. After the largest blocks are distributed, then go to smaller blocks. Never distribute a block if it would prevent a smaller block from being added without completely filling a box (for instance, if a child had a box 6 inches tall, try not to give them a five inch block since it would prevent any other block from being added to their box).

3. ## Re: Fitting Blocks into Boxes Problem

Ok, that helps. I'll go down that road for now. Any other suggestions are welcome.