Dissect a grid polygon into rectangles. (A grid polygon is a rectilinear polygon all of whose vertices have integer coordinates.)
The rectangles must be taken from a predefined set (which includes a 1×1 rectangle, so the dissection is always possible).
Each rectangle has a cost which is not directly proportional to its size (a 2×3 rectangle may cost less 'per grid square covered' than a 1×1 rectangle).
No gaps or overlaps are allowed.
The optimal solution is the cheapest that covers the area.
My first thoughts were to work out the cheapest 'per square covered' rectangle and fit as many of those into the area as possible, but it seems that might perform poorly if it means filling a lot of spaces with small, expensive pieces.
I realise this is likely NP-hard, so I am probably looking for a heuristic rather than an algorithm. It seems in some ways similar to a bin-packing problem or a knapsack problem, but I can't see how to extend the solutions to these problems. I may just be lacking the right terminology, so if anyone could point me in the right direction to get started, I'd be grateful.