As a part of a 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 we need to be able to recognize this and not use those rectangles.
Now suppose I hypothetically have an O(n^k) algorithm that solves the following problem:
"Given the list of dominoes, 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 l x w rectangle that covers as many squares as possible (i.e. a maximal orientation) in polynomial time? I want to figure out if it is possible and how fast it would be.
Some ideas (but I might be completely wrong):
Represent the squares as nodes in a graph?
Maybe something clever with DP?