You run a plant that produces sheets of aluminum alloy, and then you cut them to size for customers.

Your machine produces rectangular sheets of dimension Q $\backslash$times R$,$ and you can cut any sheet into two

smaller sheets by making a vertical or horizontal cut at an integer location. So for example, if you

have a $2\backslash$times $4$ sized piece, you have the following options that you could produce from a single cut:

$$ Two $1\backslash$times $4$ pieces $($from a horizontal cut at position $1).$

$$ Two $2\backslash$times $2$ pieces $($from a vertical cut at position $2).$

$$ A $1\backslash$times $2$ and a $2\backslash$times $3$ piece $($from a vertical cut at position $1).$

Say you decide to make the cut that produces a $1\backslash$times $2$ and a $2\backslash$times $3$ piece. You could then subsequently

cut the $1\backslash$times $2$ into two $1\backslash$times $1$ pieces, and the $2\backslash$times $3$ piece into a $2\backslash$times $1$ piece and a $2\backslash$times $2$ piece, and so on$.$

Or you could stop cutting and sell a piece that you$$ve created.

You can also rotate pieces $($so a $2\backslash$times $3$ piece is the same as a $3\backslash$times $2$ piece$).$

Suppose you produce n different sized products, where product i has dimensions xi $\backslash$times yi$,$ and you

can sell product i for vi dollars. $($For examples, perhaps product $1$ is a $2\backslash$times $2$ piece that you can sell

for $$2,$ and product $2$ is a $3\backslash$times $5$ piece that you can sell for $$3$ dollars.$)$ You can sell multiple copies

of the ith product if you can produce multiple pieces of that size from your original sheet. Assume

Q$,$ R$,$ xi$,$ yi$,$ and vi for i in $\{1,2,...,$ n$\}$ are positive integers. You will design an algorithm that figures

out your maximum profit among any possible sequence of horizontal$/$vertical cuts.

$($a$)$ Provide pseudocode for a dynamic programming algorithm that outputs your maximum profit.

$($Note: your code doesn$$t have to output how you should actually divide the piece, just the

profit.$)$ The input to your algorithm should be $($Q$,$ R$,$ x$,$ y$,$ v$)$ where Q and R are the size of the

piece, array x contains the values xi$,$ array y contains the values yi$,$ and the array v contains the

values vi$.$

$($b$)$ Explain why your algorithm is correct. $($You don$$t need to write a full proof, but you should

describe the logic behind the recurrences that you developed to create your algorithm and explain

how your algorithm checks the appropriate cases.$)$

$($c$)$ What is the runtime of your algorithm in terms of Q$,$ R$,$ and n$?$

$($d$)$ Explain briefly how you would modify your algorithm to tell you whether you should divide the

current sheet, and if so$,$ where you should make the cut