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

Given an l x w rectangle, where 1 <= l, w <= n as well as n distinct dominoes d1, d2, d3, ..., dn (each domino has a different length and width), I want to cover as much of the l x w rectangle as possible using the given dominoes. The dominoes that we place into the rectangle don't 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 have a polynomial algorithm that does the following:

Given the list of domino dimensions and the board size and a value x, this algorithm returns true if there exists some way to cover at least x squares with the dominoes and false otherwise. Let's say this algorithm runs in O(n^k) time.

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 :)