15.1 Rod cutting
15.1-1
Show that equation \(\text{(15.4)}\) follows from equation \(\text{(15.3)}\) and the initial condition \(T(0) = 1\).
- For \(n = 0\), this holds since \(2^0 = 1\).
-
For \(n > 0\), substituting into the recurrence, we have
\[ \begin{aligned} T(n) & = 1 + \sum_{j = 0}^{n - 1} 2^j \\\\ & = 1 + (2^n - 1) \\\\ & = 2^n. \end{aligned} \]
15.1-2
Show, by means of a counterexample, that the following "greedy" strategy does not always determine an optimal way to cut rods. Define the density of a rod of length \(i\) to be \(p_i / i\), that is, its value per inch. The greedy strategy for a rod of length \(n\) cuts off a first piece of length \(i\), where \(1 \le i \le n\), having maximum density. It then continues by applying the greedy strategy to the remaining piece of length \(n - i\).
The counterexample:
15.1-3
Consider a modification of the rod-cutting problem in which, in addition to a price \(p_i\) for each rod, each cut incurs a fixed cost of \(c\). The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.
We can modify \(\text{BOTTOM-UP-CUT-ROD}\) algorithm from section 15.1 as follows:
C++ | |
---|---|
1 2 3 4 5 6 7 8 9 |
|
We need to account for cost \(c\) on every iteration of the loop in lines 5-6 but the last one, when \(i = j\) (no cuts).
We make the loop run to \(j - 1\) instead of \(j\), make sure \(c\) is subtracted from the candidate revenue in line 6, then pick the greater of current best revenue \(q\) and \(p[j]\) (no cuts) in line 7.
15.1-4
Modify \(\text{MEMOIZED-CUT-ROD}\) to return not only the value but the actual solution, too.
C++ | |
---|---|
1 2 3 4 5 6 7 8 9 10 |
|
C++ | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
15.1-5
The Fibonacci numbers are defined by recurrence \(\text{(3.22)}\). Give an \(O(n)\)-time dynamic-programming algorithm to compute the nth Fibonacci number. Draw the subproblem graph. How many vertices and edges are in the graph?
C++ | |
---|---|
1 2 3 4 5 6 7 |
|
There are \(n + 1\) vertices in the subproblem graph, i.e., \(v_0, v_1, \dots, v_n\).
- For \(v_0, v_1\), each has \(0\) leaving edge.
- For \(v_2, v_3, \dots, v_n\), each has \(2\) leaving edges.
Thus, there are \(2n - 2\) edges in the subproblem graph.
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供,附加条款亦可能应用