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, soit doesn't actually matter if part of a domino we need to be able to recognize this hanging out ofd not use those rectangle. s.↵
↵
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?
↵
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
↵
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?
