patternMinor
CLRS Rod Cutting Inductive proof
Viewed 0 times
rodcuttingclrsinductiveproof
Problem
I'd like to preface this question by saying that it is not a homework question. However, it is a question regarding the course material. In the rod-cutting example an equation is presented to determine the maximum possible revenue attainable for give rod length:
$r_{n} = max(p_{i} + r_{n-i})$ (15.2)
I'm trying to prove by induction that this equation does in-fact output the optimal revenue.
It's stated that, "A simple
induction on n proves that this answer is equal to the desired answer $r_{ n}$, using
equation. 15.2"
While not required, I'm attempting to perform this induction and I'm stuck on the inductive step. Here is what I have so far:
Base Case n = 3, where $r_{n}$ represents the maximum revenue attainable from a rod of length $n$ (note the following references a price list p, which corresponds to the price of a rod for a given length, and a list r which corresponds to the maximum revenue given a rod length).
$i = 1, p_{1} + r_{3-1} = 6 $
$i = 2, p_{2} + r_{3-2} = 6 $
$i = 3, p_{3} + r_{3-3} = 8 $
Assume,
$r_{k} = max(p_{i} + r_{k-i})$
Inductive Step,
$r_{k+1} = max(p_{i} + r_{(k+1)-i})$
I'm am unclear on how to proceed from here. I realize that the optimal revenue for a give rod length is defined in terms the optimal revenue for smaller rod lengths, which I believe means this problem displays optimal sub-structure. But i'm unclear on how to proceed. I'm prefer to not be given an answer but rather some direction.
$r_{n} = max(p_{i} + r_{n-i})$ (15.2)
I'm trying to prove by induction that this equation does in-fact output the optimal revenue.
It's stated that, "A simple
induction on n proves that this answer is equal to the desired answer $r_{ n}$, using
equation. 15.2"
While not required, I'm attempting to perform this induction and I'm stuck on the inductive step. Here is what I have so far:
Base Case n = 3, where $r_{n}$ represents the maximum revenue attainable from a rod of length $n$ (note the following references a price list p, which corresponds to the price of a rod for a given length, and a list r which corresponds to the maximum revenue given a rod length).
$i = 1, p_{1} + r_{3-1} = 6 $
$i = 2, p_{2} + r_{3-2} = 6 $
$i = 3, p_{3} + r_{3-3} = 8 $
Assume,
$r_{k} = max(p_{i} + r_{k-i})$
Inductive Step,
$r_{k+1} = max(p_{i} + r_{(k+1)-i})$
I'm am unclear on how to proceed from here. I realize that the optimal revenue for a give rod length is defined in terms the optimal revenue for smaller rod lengths, which I believe means this problem displays optimal sub-structure. But i'm unclear on how to proceed. I'm prefer to not be given an answer but rather some direction.
Solution
First, be more precise in your writing. What does $\max$ range over? What is $k$ in the inductive hypothesis and step? What is the actual statement in the induction hypothesis?
In the step, you want to establish that $r_n = \dots$ is optimal assuming all $r_k$ as computed by the proposed formula for $k \leq n$ are optimal, for some fixed $n \geq 3$.
One way you typically do this is by contradiction. Assume (in addition to IH) that $\max \dots$ were not optimal. Derive that the chosen $r_k$ is not optimal either, then, which is in contradiction with the IH.
In the step, you want to establish that $r_n = \dots$ is optimal assuming all $r_k$ as computed by the proposed formula for $k \leq n$ are optimal, for some fixed $n \geq 3$.
One way you typically do this is by contradiction. Assume (in addition to IH) that $\max \dots$ were not optimal. Derive that the chosen $r_k$ is not optimal either, then, which is in contradiction with the IH.
Context
StackExchange Computer Science Q#49322, answer score: 2
Revisions (0)
No revisions yet.