ANY GENIUS HERE?
we have n x m grid and a x b rectangles
how to determine if we're able to cover whole grid with these rectangles, and if not what is the biggest ammount of rectangles which would fit?
algorithm/code would be very helpful?
halp me pls
I believe that this is the criteria for tiling the whole grid, but correct me if I'm wrong.
Each of a and b must divide either n or m (they may divide the same number or different numbers). If they divide the same number, say a | n and b | n, then you must have m = ax + by for some non negative integers x,y.
Do all the rectangles have the same size?
If they do than it's easy. max(floor(m/b)*floor(n/a), floor(m/a)*floor(n/b)) is the maximum number of rectangles can fit in the m x n grid.
Then you can just fit all of those rects into the grid, if there is any empty space left, then it's impossible to cover the grid with those a x b rectangles.
If the rectangles are not equal in size, then I have a bad news for you.
To get the optimal solution, you have to run the algorithm for quite a long time.