Question

Cutting cloth. You are given a rectangular piece of cloth with dimensions $\mathit{X}\mathbf{\times }\mathit{Y}$, where$\mathit{X}$ and $\mathit{Y}$are positive integers, and a list of products that can be made using the cloth. For each product$\mathit{i}\mathbf{}\mathbf{\in }\mathbf{}\left[1,n\right]$ you know that a rectangle of cloth of dimensions${\mathbf{a}}_{\mathbf{i}}\mathbf{\times }\mathbf{}{\mathbf{b}}_{\mathbf{i}}$ is needed and that the final selling price of the product is ${\mathit{c}}_{\mathbf{i}}$. Assume the,${\mathit{a}}_{\mathbf{i}}$ ${\mathit{b}}_{\mathbf{i}}$and${\mathit{c}}_{\mathbf{i}}$ are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design an algorithm that determines the best return on the$\mathit{X}\mathbf{\times }\mathit{Y}$ piece of cloth, that is, a strategy for cutting the cloth so that the products made from the resulting pieces give the maximum sum of selling prices. You are free to make as many copies of a given product as you wish, or none if desired.

Short answer

Using dynamic programming, the required algorithm can be implemented with time complexity $O\left(XY\left(X+Y+n\right)\right)$.

Step-by-step solution

Defining recursive relation

Consider$\text{CUT}\left(i,j\right)$ be the cut made in order to make maximum selling cost.

Base case is when no cut is made,$i=j=0$ which give $\text{CUT}\left(i,j\right)=0$.

To cut horizontally, along$x$, the recursive relation is

$\text{CUT}\left(i,j\right)=\text{max}\left(\text{CUT}\left(i,j\right),\text{CUT}\left(i_{cut},j\right)+\text{CUT}\left(i-i_{cut},j\right)\right)$

To cut vertically, along,$y$ the recursive relation is

$\text{CUT}\left(i\text{,\hspace{0.33em}}j\right)=\text{max}\left(\text{CUT}\left(i\text{,\hspace{0.33em}}j\right),\text{CUT}\left(i\text{,\hspace{0.33em}}{j}_{cut}\right)+\text{CUT}\left(i,j-j_{cut}\right)\right)$

From these two recurrence relation, dimension of cloth required to make maximum selling price.

Determine an algorithm

The algorithm is given as follows:

$\begin{array}{l}\text{for}\left(i=0\text{\hspace{0.33em}to}x-1\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}for}\left(j=0\text{\hspace{0.33em}to\hspace{0.33em}}Y-1\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}for}\left(i_{cut}=1\text{\hspace{0.33em}to\hspace{0.33em}}i-1\right)\\ CUT\left(i,j\right)=\text{max}\left(CUT\left(i,j\right),CUT\left(i_{cut},j\right)+CUT\left(i-i_{cut},j\right)\right)\end{array}$

$\begin{array}{l}\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}for}\left(j_{cut}=1\text{\hspace{0.33em}to}j-1\right)\\ CUT\left(i,j\right)=\text{max}\left(CUT\left(i,j\right),CUT\left(i,j_{cut}\right)+CUT\left(i,j-j_{cut}\right)\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}for}\left(\text{item\hspace{0.33em}inITEMS}\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}if}\left(ite{m}_{dimension}=\left(i,j\right)\right)\\ CUT\left(i,j\right)=\text{max}\left(CUT\left(i,j\right),c_i\right)\\ \text{return\hspace{0.33em}}CUT\left(X-1,Y-1\right)\end{array}$

The algorithm returns the desired size of cloth need to earn maximum selling price.

Analyse the run time of the algorithm 

The inner three $for\left(\right)$loops run$X,Y$ and$n$ times, so runtime for inner loops are $O\left(X+Y+n\right)$Now outer loops run in nesting, that give $O\left(XY\right)$.

Thus, effective runtime is $O\left(XY\left(X+Y+n\right)\right)$.