78 lines
1.7 KiB
Markdown
78 lines
1.7 KiB
Markdown
# 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 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
|
| ------ | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|
|
| $p[i]$ | 0 | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
|
|
| $r[i]$ | 0 | 1 | 5 | 8 | 10 | 13 | 17 | 18 | 22 | 25 | 30 |
|
|
| $s[i]$ | 0 | 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
|
|
|
|
```text
|
|
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
|
|
|
|
```text
|
|
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
|
|
|
|
```text
|
|
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
|
|
``` |