patternMinor
What is the formal justification for the correctness of the second formulation of rod cutting DP solution
Viewed 0 times
therodwhatcuttingformalcorrectnessforjustificationsecondsolution
Problem
CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference.
Define $r_j$ to be the optimal way to cut a rod of integer length $j$.
Since we do not know where is the optimal place to cut the rod we consider every location $ i \in \{0,\cdots,j\}$ (essentially doing exhaustive search) to do the cut. Then we are left with two rods of length $i$ and $j-i$ to cut optimally.
If we consider every location we could do a cut and then cut the remaining rods optimally, then we have essentially solved $r_j$ optimally. i.e. we get the following recursion:
$$ r_j = \max \{p_n, r_1 + r_{k-1}, r_2 +r_{j-2}, ..., r_{j-1} + r_1 \}$$
However there seems to be an alternative (or maybe simpler strategy to solve such a problem):
$$r_n = \max_{1 \leq i \leq n} \{ p_i + r_{n-i} \}$$
CLRS has the following discussion about it:
In a related, but slightly simpler, way to arrange a recursive
structure for the rod- cutting problem, we view a decomposition as
consisting of a first piece of length $i$ cut off the left-hand end,
and then a right-hand remainder of length $n -i$. Only the remainder,
and not the first piece, may be further divided. We may view every
decomposition of a length-n rod in this way: as a first piece followed
by some decomposition of the remainder. When doing so, we can couch
the solution with no cuts at all as saying that the first piece has
size $i = n$ and revenue $p_j$ and that the remainder has size $0$
with corresponding revenue $r_0 = 0$.
In this formulation, an optimal solution embodies the solution to only one related subproblem-the remainder-rather than two.
Personally I've always found it harder to convince myself that this in fact optimal (and that is therefore equivalent to the first one). Therefore I was wondering if anyone had a good argument or maybe a good formal proof to arguing why this second formulation is in fact optimal.
Usually I
Define $r_j$ to be the optimal way to cut a rod of integer length $j$.
Since we do not know where is the optimal place to cut the rod we consider every location $ i \in \{0,\cdots,j\}$ (essentially doing exhaustive search) to do the cut. Then we are left with two rods of length $i$ and $j-i$ to cut optimally.
If we consider every location we could do a cut and then cut the remaining rods optimally, then we have essentially solved $r_j$ optimally. i.e. we get the following recursion:
$$ r_j = \max \{p_n, r_1 + r_{k-1}, r_2 +r_{j-2}, ..., r_{j-1} + r_1 \}$$
However there seems to be an alternative (or maybe simpler strategy to solve such a problem):
$$r_n = \max_{1 \leq i \leq n} \{ p_i + r_{n-i} \}$$
CLRS has the following discussion about it:
In a related, but slightly simpler, way to arrange a recursive
structure for the rod- cutting problem, we view a decomposition as
consisting of a first piece of length $i$ cut off the left-hand end,
and then a right-hand remainder of length $n -i$. Only the remainder,
and not the first piece, may be further divided. We may view every
decomposition of a length-n rod in this way: as a first piece followed
by some decomposition of the remainder. When doing so, we can couch
the solution with no cuts at all as saying that the first piece has
size $i = n$ and revenue $p_j$ and that the remainder has size $0$
with corresponding revenue $r_0 = 0$.
In this formulation, an optimal solution embodies the solution to only one related subproblem-the remainder-rather than two.
Personally I've always found it harder to convince myself that this in fact optimal (and that is therefore equivalent to the first one). Therefore I was wondering if anyone had a good argument or maybe a good formal proof to arguing why this second formulation is in fact optimal.
Usually I
Solution
The proof of $r_n = \max_{1 \leq i \leq n} (p_i + r_{n-i})$ is divided into two parts. In the first part, we prove that $r_n \geq \max_{1 \leq i \leq n} (p_i + r_{n-i})$. In the second part, we prove that $r_n \leq \max_{1 \leq i \leq n} (p_i + r_{n-i})$.
First part. It suffices to prove that for each $1 \leq i \leq n$, $r_n \geq p_i + r_{n-i}$. Indeed, consider first breaking the rod into a piece of size $i$ and a piece of size $n-i$, and then cutting the second piece optimally. This strategy guarantees a profit of $p_i + r_{n-i}$.
Second part. It suffices to prove that for some $1 \leq i \leq n$, $r_n \leq p_i + r_{n-i}$. Consider any way of cutting the rod. Let $i$ be the size of the leftmost piece, which results in a profit of $p_i$. The other pieces (if any), put together, form a rod of size $n-i$, and so the profit gained from them is at most $r_{n-i}$. In total, the profit is at most $p_i + r_{n-i}$. In particular, the optimal profit $p_n$ is at most $p_i + r_{n-i}$.
First part. It suffices to prove that for each $1 \leq i \leq n$, $r_n \geq p_i + r_{n-i}$. Indeed, consider first breaking the rod into a piece of size $i$ and a piece of size $n-i$, and then cutting the second piece optimally. This strategy guarantees a profit of $p_i + r_{n-i}$.
Second part. It suffices to prove that for some $1 \leq i \leq n$, $r_n \leq p_i + r_{n-i}$. Consider any way of cutting the rod. Let $i$ be the size of the leftmost piece, which results in a profit of $p_i$. The other pieces (if any), put together, form a rod of size $n-i$, and so the profit gained from them is at most $r_{n-i}$. In total, the profit is at most $p_i + r_{n-i}$. In particular, the optimal profit $p_n$ is at most $p_i + r_{n-i}$.
Context
StackExchange Computer Science Q#56552, answer score: 3
Revisions (0)
No revisions yet.