As a part of a research project, I am troubled with the following problem:

Given an l x w rectangle, where 1 <= l, w <= n as well as n dominoes d1, d2, d3, ..., dn (each domino has a length and width which don't necessarily need to be different), I want to cover as much of the l x w rectangle as possible using the given dominoes.

The dominoes that are placed into the rectangle don't necessarily need to be small enough to fit inside of the rectangle, so it doesn't actually matter if part of a domino is hanging out of the rectangle.

Now suppose I hypothetically have an O(n^k) algorithm that solves the following problem:

"Given the list of domino dimensions, the rectangle dimensions (l and w) and some value x, this algorithm returns true if there exists some way to cover at least x squares with the dominoes and the algorithm returns false otherwise."

Now using this algorithm, is it possible to find a tiling of the a x b rectangle that covers as many squares as possible (i.e. a maximal orientation) How fast?

I think the answer is no right now but I just can't think of it so that's my reason. Maybe someone smarter than me can think of something :)