Compute how to subdivide an n m marble slab to maximize your profit

Question

You have mined a large slab of marble from your quarry. For simplicity, suppose the marble slab is a rectangle measuring n inches in height and m inches in width. You want to cut the slab into smaller rectangles of various sizes – some for kitchen countertops, some for large sculpture projects, others for memorial headstones. You have a marble saw that can make either horizontal or vertical cuts across any rectangular slab. At any given time, you can query the spot price px,y of an x y marble rectangle, for any positive integers x and y. These prices will vary with demand, so do not make any assumptions about them. Given the spot prices, describe an algorithm to compute how to subdivide an n m marble slab to maximize your profit.

Answer 1

Let $M[n,m]$ represent the maximum profit that can be obtained by subdividing an $n \times m$ marble slab. Then using the provided spot price function $p(x,y)$, we observe that if $n=0$ or $m=0$, then $M[n,m] = 0$; otherwise, we have that $M[n,m]$ is: $$ \max\left\{p(n,m),~~\max\limits_{1\leq i\leq \left\lfloor\frac{n}{2}\right\rfloor}\{M[i,m] + M[n-i,m]\},~~\max\limits_{1\leq j\leq \left\lfloor\frac{m}{2}\right\rfloor}\{M[n,j] + M[n,m-j]\}\right\} $$ Intuitively, this is saying that we can either sell the entire slab, make some horizontal cut, or make some vertical cut. We describe this recursion by using the following dynamic programming algorithm:

COMPUTE-M(n,m,p,M)
    if (M[n][m] != NIL) then:
        return // Don't redo work.
    else if (n == 0  or  m == 0) then:
        M[i][j] <- 0 // Base Case.
    else:
        max <- 0
        for i <- 1 to floor(n/2) do: // Check all horizontal cuts.
            COMPUTE-M(i,m,p,M)
            COMPUTE-M(n-i,m,p,M)
            if (M[i][m] + M[n-i][m] > max) then:
                max <- M[i][m] + M[n-i][m]
        for j <- 1 to floor(m/2) do: // Check all vertical cuts.
            COMPUTE-M(n,j,p,M)
            COMPUTE-M(n,m-j,p,M)
            if (M[n][j] + M[n][m-j] > max) then:
                max <- M[n][j] + M[n][m-j]
        if (p(n,m) > max) then: // Should we just sell the entire slab?
            max <- P(n,m)
        M[n][m] <- max

Finally, we initiate everything using the following:

SUBDIVIDE(n,m,p)
    // Initialize M to be completely NIL.
    for i <- 0 to n do:
        for j <- 0 to m do:
            M[i][j] <- NIL
    COMPUTE-M(n,m,p,M)
    // Return the maximum profit and the list of slabs.
    return M[n][m]