Typical mistakes · In summary¶

28.4 Typical mistakes¶

Warning

Counting vectors instead of cutting patterns. The \(2^{n-1}\) cutting patterns of a rod of length \(n\) are more than the solution vectors when \(n\ge 3\), because different patterns can give the same vector.
Forgetting the base case. \(v(0)=0\) is used when the first piece has the length of the whole rod: \(v(\ell)\) contains the term \(p_\ell+v(0)\).
Using row \(j-1\) in the second recurrence. The term \(p_j+v(j,\ell-j)\) stays in row \(j\): otherwise a piece length could be cut only once.
Stopping the reconstruction early. The rule \(x_{{s}[\ell]}\leftarrow x_{{s}[\ell]}+1\), \(\ell\leftarrow\ell-{s}[\ell]\) is repeated until \(\ell=0\); the last piece completes the rod.

In summary

The RCP asks how to cut a rod of length \(n\) into pieces, with each length available any number of times, to maximize the total profit.
The recurrence \(v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}\) has the optimal substructure and overlapping subproblems, and \(v(0)=0\).
The vector \(v\) is filled bottom-up in \(\Theta(n^2)\) steps, which is polynomial because the input has \(n\) profits.
The vector \({s}\) of the first pieces gives an optimal solution for every rod length at no extra cost.

Dashboard of the RCP example. Example 28.1 (rod of length \(4\)):

Method	Lower bound	Upper bound	Origin
DP algorithm	\(10\)	\(10\)	optimal value, two pieces of length \(2\)

Exercises on this chapter: Rod cutting (RCP)