Given a polygon and dimension $d$, find a minimum partition of rectangles that has either of its dimensions equal to $d$.

Example: Consider the following diagram:

I want to cover maximum shaded region using minimum number of rectangles of fixed one dimension (width or height). In other words, one dimension of all the rectangles should be the same. Rotated rectangles are not allowed. We can leave empty space if required near the inclined edge. No overlapping is allowed.

My attempt was to use a linear program to solve this problem. However, I'm stuck at the very beginning to put a restriction on the number of rectangles. I thought of declaring a binary variable $m_i, i \in \{1, 2, ..., N \}$, where $m_i=1$ shows that $i$th rectangle is present out of $N$ available rectangles. The solution breaks down if my solution requires more number of rectangles than $N$. My questions are as follows:

- Is linear programming the only way to solve this problem? Can I use some other algorithm to solve it?
- If linear programming is the only way, how should I handle the varying number of rectangles in the linear program?

2more comments