Results 1 to 3 of 3

Math Help - Fitting Blocks into Boxes Problem

  1. #1
    Newbie
    Joined
    Apr 2014
    From
    United States
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    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).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2014
    From
    United States
    Posts
    2

    Re: Fitting Blocks into Boxes Problem

    Ok, that helps. I'll go down that road for now. Any other suggestions are welcome.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: January 2nd 2013, 04:23 PM
  2. Physics Problem: Two blocks stacked
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: November 18th 2011, 02:25 AM
  3. empty boxes problem help
    Posted in the Algebra Forum
    Replies: 4
    Last Post: August 27th 2010, 04:25 PM
  4. triangular blocks problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: January 16th 2010, 11:54 PM
  5. A balls and boxes problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2008, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum