Kite-cutting : More on dynamic programming – 4

Question. We are given a sheet of rectangular paper of length L and width W (where L and W are integral). We need to cut it in order to make rectangular kites. We have a set of n types of kites, each of integral dimensions, which we can make. Kite i has length l_i, width w_i and sells for a profit of p_i. As is obvious, we would like to maximize the profit we can make from our rectangular sheet of paper.

Now, we are given a cutting device to cut the sheet. The cutting device can cut a sheet of paper only either horizontally or vertically. What this means is that we cannot cut a sheet into arbitrary shapes. Given a rectangular sheet to start with, the above condition implies that we will always obtain 2 smaller rectangles from it. The smaller rectangles can be obtained by either cutting along the width or along the length.

Also, we are told that there is no restriction on the number of kites we are allowed to make of any particular type.

Solution.

We can solve this in a fairly straightforward fashion using dynamic programming.

Let’s denote by OPT(x,y) the maximum profit we can derive out of a sheet of paper of length x and width y.

Thus, our aim is to compute OPT(L,W).

Now, we know that we can cut the x \times y dimension sheet only either along its length or along its width (or we can also choose not to cut the sheet at all).

If we cut along the length, the 2 smaller rectangles obtained are of sizes: x \times w and x \times (y-w) where w lies in the range \{1, y-1\}.

Similarly, one can cut width-wise.

Also, let us denote by P(x,y) the profit we would get if by directly selling (i.e. without cutting) our x \times y sheet of paper. (Note that this means that there exists some kite-type which has exactly these dimensions.)

——

We obtain the following recurrence based on the above observations:

OPT (x,y) = \max \{ Term 1, Term 2, P(x,y) \}.

Term1 = \{ OPT(x, w) + OPT(x,y-w) : w \in \{1, \ldots, y-1\} \}.

Term2 = \{ OPT(l, y) + OPT(x-1, y) : l \in \{1, \ldots, x-1\} \}.

——-

Further, we have the following obvious results:

OPT(0, y) = 0 for all y.

OPT (x, 0) = 0 for all x.

——–

Using the above recurrence, we can compute the OPT table as follows:

——

// in C++

//we assume we have already computed P[x][y].

int OPT[L]{W];

for (int i = 0; i < L; i++)

OPT[i][W] = 0;

for ( i =0; i < W; i++)

OPT [L][i] = 0;

int j, k, temp1 = 0, temp2 = 0, max;

for (i = 0; i < L; i++)

for (j=0; j < W; j++)

{

for (k =1; k < i ; k++)

{

if (OPT[k][j] + OPT[i-k][j] > temp1)

//temp1 stores the max value of term1

temp1 = OPT[k][j] + OPT[i-k][j];

}

for ( k = 1; k < j; k++)

{

if ( OPT[i][k] + OPT [i][j-k] > temp2)

//temp 2 stores the max value of term2

temp2 = OPT[i][k] + OPT [i][j-k];

}

//now take the max of temp1, temp2 and P[i][j].

max = (temp1 > temp2) ?temp1 : temp2;

OPT[i][j] = (max > P[x][y]) ? max : P[x][y];

}

———

The answer that we want is OPT[L][W].

The above code would run in time O(L^2 W^2).

(Note that we assume P[x][y] values to be part of the input.)

——-



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: