Expert: Scott A Wilson - 11/25/2011

Question
QUESTION: Good day,
Here's my question.
Let us say I have rectangle pieces packed in a larger rectangle (strip) with fixed width and variable height.
__________________________________
|128*32          |64*64   |64*32   |
|________________         |________|
|128*64          |        |64*32   |
|          |________|________|
|          |          |
|________________|___          |
|160*32          |          |
|____________________|_____________|

This is a strip packing problem. let us assume the height has value already.
How do we compute the area occupied by the rectangle pieces?
and How do we compute the wasted space of the larger rectangle(strip)?

Thank you very much.

Well, basically my question is because of this pdf file http://www.cs.nott.ac.uk/~ekb/Publications/sim.pdf

The part where solution evaluation is stated.

"Solution Evaluation = Total Height + (Area Under Skyline / Sheet Width)"

I wanna know how to compute about the "Area Under Skyline" they are talking about.

Hope you can help me. Thank you very much.
I look forward to hearing from you the soonest. :)

ANSWER: A graph was sent back, since it cam through poorly as
|128*32          |64*64   |64*32   |
|________________         |________|
|128*64          |        |64*32   |
|          |________|________|
|          |          |
|________________|___          |
|160*32          |          |
|____________________|_____________|



---------- FOLLOW-UP ----------

QUESTION: Yes, that's the correct image. Thank you. But don't worry it is just example image for my description of the problem to be clearer. The dimensions really don't matter. :)

Hope you could help me answer my question(s). Most importantly on the pdf one :) Thank You.

Answer
O sent the graph as an attachment again, but this time made it larger.

The image you sent looks like

___________________________________
|128*32          |64*64   |64*32   |
|________________         |________|
|128*64          |        |64*32   |
|          |________|________|
|          |          |
|________________|___          |
|160*32          |          |
|____________________|_____________|
After viewing it in the attached supplement, it looks like the 128x32 lies right above the 128x64.  It then looks like the 64x64 lies right above the 64x32, and both of these lie to the right of the first two.  Up in the top, there is another 64x32.  At the bottom on the left, over on the left, there is as 160x32.

There are 7 squares that are left over (each of them is 32x32) of the same size left over that are not in any figure.

If the 64x32 at the right side on the top is moved down below the 160x32, the entire rectangle would be 192x160, with only 5 squares (32x32) left unused.

An even better plan might be to take the rectangle on the top right and turn it 90 degrees, so it is 64 high and 32 wide.  This would make the rectange that included all of the shapes only have 3 blank squres unused.

It then occured to me that since we have 25 32x32 squares in these shapes, we could put the 128x32 on top, the 128x64 below that, and another 128x64 space below that.  The space on the bottom would have the 64x64 on the left and the two 64x32 shapes on the right.  The remaining shape, the 160x32, would be on the right going up and down from top to bottom.  This would use all squares in the design.