Help needed, can't solve this one .

general
, ,
1

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

2

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
3

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]);
                }
            }
        }
    }

i am getting wrong answer.
please see it.

4

thanks @mogers.