rectangles in rectangle problem
- Home
- Board: /sci/ - Science & Math
- Reading: rectangles in rectangle problem
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?
thanks
halp me pls
all rectangles are the same size
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.
Engineer here (sorry).
Does this help?http://www.rmig.com/en/technical+info/formulae/calculation+open+area
>>7778243
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.
https://en.wikipedia.org/wiki/Cutting_stock_problem
To get the optimal solution, you have to run the algorithm for quite a long time.