Review 8-2

Hajin Ju, 2024062806

Problem 1

Fill in the blanks in the table below.

p[i]: the price for a rod of length i
r[i]: the maximum revenue for a rod of length i
s[i]: the length of the leftmost piece when the revenue is maximum

Solution 1

i	1	2	3	4	5	6	7	8	9	10
`p[i]`	1	5	8	9	10	17	17	20	24	30
`r[i]`	1	5	8	10	13	17	18	22	25	30
`s[i]`	1	2	3	2	2	6	1	2	3	10

Problem 2

Fill in the blanks in the following pseudocode for EXTENDED-BOTTOM-UP-CUT-ROD.

Solution 2

EXTENDED-BOTTOM-UP-CUT-ROD (p, n)
    let r[0..n] and s[0..n] be new arrays
    r[0] = 0
    for j = 1 to n
        r[j] = -inf
        for i = 1 to j
            if r[j] < p[i] + r[j-i]
                r[j] = p[i] + r[j-i]
                s[j] = i
    return r, s

Problem 3

Fill in the blanks in the following pseudocode for PRINT-CUT-ROD-SOLUTION.

Solution 3

PRINT-CUT-ROD-SOLUTION (p, n)
    (r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    while n > 0
        print s[n]
        n = n - s[n]

Problem 4

Fill in the blanks in the following pseudocode for M-CUT-ROD.

Solution 4

M-CUT-ROD (p, n)
    let r[0..n] be a new array
    for i = 0 to n
        r[i] = -inf
    return M-CUT-ROD-A(p, n, r)

M-CUT-ROD-A (p, n, r)
    if r[n] >= 0
        return r[n]
    if n == 0
        return 0
    else q = -inf
        for i = 1 to n
            q = max(q, p[i] + M-CUT-ROD-A(p, n-i, r))
    r[n] = q
    return q

1.7 KiB Raw Permalink Blame History