An algorithm for pavement usage calculation

Given an area of spec开发者_Python百科ific size I need to find out how many pavement stones to use to completely pave the area. Suppose that I have an empty floor of 100 metre squares and stones with 20x10 cm and 30x10 cm sizes. I must pave the area with minimum usage of stones of both sizes. Anyone knows of an algorithm that calculates this?

(Sorry if my English is bad)

C# is preferred.

This is a category of problem known as a Packing Problem.

This DevX article provides background and outlines approaches without directly solving the homework for you (it also provides code, but you'll have to think a bit to apply it to your situation).

You can solve this in your head (assuming the area to fill is rectangular). If you have to fill an area of N squares, and your tiles are 2x1 and 3x1, you never need more than two 2x1 tiles. This gives the total number of tiles you need to be N/3 (rounded up) except for the case N=1 which is impossible.

Proof: Suppose your area is A x B and that not both of A and B are 1. Assume without loss of generality that A != 1.

You can tile a rectangular area A x 3 with 3x1 tiles easily. Repeat this pattern to fill up the are as much as possible. If there are no rows left, you're done (you've tiled the entire area with 3x1 tiles) If there's one row left, fill with 3x1 tiles until you have either 0, 1 or 2 spaces left. 0 => you're done, 1 => replace the last 3x1 with two 2x1, 2 => fill the last square with a 2x1. If there's two rows left, do a similar construction. You'll be left with either 0 columns (you're done), 1 column (fill it with a 2x1), or 2 columns (fill it with two 2x1).