minimum number tiles within given rectangle

I开发者_如何学JAVA have been practicing some programming contest questions (for fun and practice for upcoming contests) and am stuck on this one: http://dwite.ca/questions/power_tiles.html

I'm not really sure where I should start =/. How should I approach this question in order to solve it?

Looks like a Dynamic Programming problem to me

• Let F(w,h) be the minimum number of squares that tile the w by h rectangle.

• Find a recursive formulation for F:

  • if w = 0 or h = 0 then F(w, h) = 0

  • otherwise, F(w,h) =

    For each allowable size a=i^2 <= min(w,h), try to place the a by a square (A)
     in the top left corner.
    One of the following possibilities will describe the
     optimal solution:
     +---+--+    +---+--+
     | A | C|    | A |  |
     +---+--+    +---+  |
     |  B   |    |B  |C |
     +------+    +---+--+
     So, choose the best of
       (1 + F(h-a, w) + F(h-a, w-a)) or
       (1 + F(h-a, a) + F(w-a, h))
    

Doing big-O analysis on a napkin, this seems to be an O(side^2 * sqrt(side))-ish algorithm. If this is too much, you can:

• Try to exploiti symmetries in the problem (such as F(w,h) = F(h, w))
• Check the analysis again to be sure it is too slow and you need another algorithm (perhaps you don't need to calculate for all (w,h) pairs?)
• Find some property of the problem that allows for a simpler, less exaustive strategy. (For example, picking the largest square whenever possible is a simple greedy strategy... but does it work in all cases?)

I would approach it by recursion.

Write a function that receives two integer values as its inputs. The one value would be the length and the other would be the width. The biggest square you could fit in would be based on the shortest side. Its dimensions would be calculated as follows:

2^RoundDown(Log(ShortSide,Base:2))

This will give you your first square and divide the rectangle up in either 3 or 1 other rectangles, or nothing if it is square with 2^n side lengths.

It is easy to get the dimensions of the remaining rectangles by simple subtraction. After the dimensions are calculated, call the function again(within itself) for each new rectangle with its dimensions.

The function should be terminated when the differences calculated for both sides are zero, i.e. it is square with 2^n side lengths.

A bit like this:

Global int Counter
DivideRectangle(int Width, int Length)
    int BigSquare = 2^RoundDown(Log(Width,Base:2))
    if NOT(Width - BigSqaure = 0 AND Height- BigSqaure = 0)
        DivideRectangle(width - BigSquare, Height - BigSquare)
        DivideRectangle(width - BigSquare, BigSquare)
        DivideRectangle(BigSquare, Height - BigSquare)

    Counter += 1

That's about the just of it; the counter returned after the whole operation is the the number of squres to fill the rectangle. Obviously the code is flawed and needs refinement but it's just an outline of what should happen.

What '1, 2, 4, 8, etc' do remember you?

Look at the figure, what is the order (in sterm of size) of filling you will choose?

I would start by figuring out the answer by hand to say a half dozen or so... then model how you did the problem in a program... Then after you have a working "brute force" answer try to solve the problem more elegantly.

I would start this problem by trying to put as many of the bigest size tiles in first then fill in where you can with the next bigest size that will fit. then smaller... until filled.

You might use Arrays or arrays to spacially keep track of the filled in space... however I suspect there is an easier way to do this via some simple calculations... like taking the dimensions and take the smaller of the two and utilizing log base 2 or something like that...

I am sure there is a nice neat recursive solution.. base on the powers of two .. then you could unravel that into a non-recursive solution...