I am working in a printing press and would like to maximize the usage of an arbitary size of paper.
Suppose I have a paper (large rectangle $A$) sized $x×y$ mm, and I have a product (tiny rectangle $B$) sized $a×b$ mm. Of course, $x>a>0$ and $y>b>0$.
How many copies of products can I cut out of this paper (whether landscape or portrait or a mixture of them) and how should I cut them? How many of the products should be landscape and how many of them should be portrait?
I have a program that helps me making those decisions but I wonder how it actually worked. The sample data output by the program can be seen here.
In the above screenshot, $x=1200$, $y=1000$, $a=432$, $b=278$. The output is a total of $9$ products can be put onto the paper, $5$ portrait and $4$ landscape, with a usage rate at $90.07\%$.
Be $\Omega$ the set of all the valid scenarios and be $C(\vec{s})$ the area covered if $\vec{s}$ was chosen, then $$ S = \{\vec{s} \in \Omega : C(\vec{s}) = \max_{\vec{s_0} \in \Omega} C(\vec{s_0})\} $$ is the set of the layouts that maximise the coverage of $A$. While easier to define, this is highly inefficient and not guaranteed to end its execution.
Since $C(\vec{s}) \leq xy$ for any problem then it makes sense to define $R(\vec{s}) = xy - C(\vec{s}) \geq 0$ as the area uncovered if $\vec{s}$ was chosen. Given a set $\Omega_n$ of scenarios generated by an algorithm $A_n$ where $\vec{s}_1 \in \Omega_n$, if $R(\vec{s}_1) < ab$ holds then it must be $\vec{s}_1 \in S$.
The algorithm $A_\star$ we need is the one that guarantees that there is at least an element $\vec{s}_2$ of $\Omega_\star$ that satisfies $R(\vec{s}_2) < ab$ for any problem. It does not matter that $\Omega_\star \subset \Omega$ and that $\Omega_\star \neq S$: $R(\vec{s}) < ab$ guarantees that $\vec{s}$ is the greatest effort we can make to minimize the waste of paper.
That’s what it is all about. What happens next is the research of those algorithms and the conditions that satisfies $R(\vec{s}) < ab$ for at least one $\vec{s}$ of $\Omega_A$. We’ll see only the easiest.
The “tiling” way - Imagine you’re tiling a floor of the same dimensions of $A$ with tiles that have the size of $B$: given you want to cover the greatest area possible, how would you do?
Be $(a, b)$ the first guess, then the number of tiles $N_1$ that fit inside a floor of size $(x,y)$ is : $$N_1 = \left\lfloor\frac{x}{a}\right\rfloor\left\lfloor\frac{y}{b}\right\rfloor$$ Swapping $a$ and $b$ give $N_2$ which is: $$N_2 = \left\lfloor\frac{x}{b}\right\rfloor\left\lfloor\frac{y}{a}\right\rfloor$$
Then: $$ \begin{align} R(\vec{s}_1) &= xy - ab\cdot N_1 \\ R(\vec{s}_2) &= xy - ab\cdot N_2 \end{align} $$
Depending on the values of $R(\vec{s}_1)$ and $R(\vec{s}_2)$ we’ll know what to do next:
Conclusion - The previous algorithm was very naive indeed, yet it can be useful and fast if at least one of the above conditions are met (I think those conditions could be joined into a single statement for an even faster evaluation). I don’t know if there is actually an unique algorithm that can be employed, nonetheless whenever we run out of algorithms for a given scenario it is sufficient to derive a particular algorithm for that single scenario and to add it to the list of known algorithms.
What could be investigated now is how to build the sets $\Omega_n \subset \Omega$ (so that $\bigcup_n \Omega_n = \Omega$) given every $\Omega_n$ is generated by a single algorithm $A_n$ for which a single statement $T_n$ exists so that if $T_n$ is true then $A_n$ raise at least a scenario $\vec{s}_\star$ so that $R(\vec{s}_\star) < ab$.
Finally the algorithm $A_\star$ is the one that chooses an $A_n$ testing every known $T_n$: then $\Omega_\star = \Omega$ so $A_\star$ succeeds for any problem.