 # Help needed, can't solve this one .

I googled the problem and found the solution, but I was not able to understand the recurrence relation.Any help will be appreciated.

If we’re not able to cut a slab with height H and width W is H*W.

Suppose we have a slab of size H*W.

``````+-------------------+
|                   |
|                   |   H
|                   |
+-------------------+
W
``````

If we cut a plate of size y*x,

``````                x
+-------------------+
|         y |_ _ _ _|
|                   |   H
|                   |
+-------------------+
W
``````

then the waste is the minimum of splitting the slab into 2 of sizes H * (W-x) and (H-y) * x

``````                x
+-------------------+
|         y |_ _ _ _|
|           |       |   H
|           |       |
+-------------------+
W
``````

or splitting into y * (W-x) and (H-y)*W

``````                x
+-------------------+
| _ _ _ _ y |_ _ _ _|
|                   |   H
|                   |
+-------------------+
W
``````

We can see that the slab splits are always made into smaller pieces, so a bottom-up dynamic programming algorithm can reuse the minimum cost of splitting smaller slabs.

3 Likes

thanks @mogers.

I have used 3D dp in this case i.e dp[i][j][k]
where dp[i][j][k] means i have to maximize utilization of (i X j) rectangle with k options
and i have given the answer as w*h - dp[w][h][n].

``````    lp(i,1,wd+1){
lp(j,1,ht+1){
lp(k,1,n+1){
dp[i][j][k] = dp[i][j][k-1];
if(i>=w[k] && j>=h[k]){
dp[i][j][k] = max(dp[i][j][k],dp[i-w[k]][j][k] + dp[w[k]][j-h[k]][k] + w[k]*h[k]);
dp[i][j][k] = max(dp[i][j][k],dp[i][j-h[k]][k] + dp[i-w[k]][h[k]][k] + w[k]*h[k]);
}
}
}
}
``````