Kite-cutting : More on dynamic programming – 4
February 15, 2011 Leave a comment
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 , width and sells for a profit of . 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.
We can solve this in a fairly straightforward fashion using dynamic programming.
Let’s denote by the maximum profit we can derive out of a sheet of paper of length x and width y.
Thus, our aim is to compute .
Now, we know that we can cut the 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: and where lies in the range .
Similarly, one can cut width-wise.
Also, let us denote by the profit we would get if by directly selling (i.e. without cutting) our 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:
Further, we have the following obvious results:
for all .
for all .
Using the above recurrence, we can compute the OPT table as follows:
// in C++
//we assume we have already computed P[x][y].
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.)