MHB Optimizing Block Distribution for Children's Boxes: A Computational Approach

[Thread7]

I'm sorry if this isn't the correct forum. I wasn't sure where to put it. 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.

Thanks in advance!

 

[I like Serena]

I'm sorry if this isn't the correct forum. I wasn't sure where to put it. 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.

Thanks in advance!

Welcome to MHB, Thread7! :)

Basically you have to indeed loop through every combination until something works.
However, you can optimize the procedure quite a bit.

The method is called backtracking.
See for instance wiki: https://en.wikipedia.org/wiki/Backtracking

The principle is that we systematically verify each combination block by block.
Once we find a block that no longer fits, we do not try to continue with the other blocks, which is what your proposed algorithm would do.
Instead we "backtrack".
We take the last block that did not fit back, and try another block.
Then we take the last 2 blocks back that did not fit, and so on.

 

[Thread7]

Ok, this helps. I was hoping it wouldn't be that resource intensive. I'll proceed down the backtracking route and if anyone has other comments please chime in.