Rod-Cutting Problem (Rod-Cutting Problem)

From Algorithm Wiki
Revision as of 09:11, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


Given a rod of length $n$, and prices $p_i$ for which one can sell a segment of the rod of length $i$ ($1 \leq i \leq n$), find the splitting of the rod for which one can earn the most money once they sell the rod segments produced.


$n$: length of rod

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Brute Force 1940 $O(n*{2}^n)$ $O(n)$ Exact Deterministic
Dynamic Programming 1953 $O(n^{2})$ $O(n)$ Exact Deterministic

Time Complexity Graph

Rod-Cutting Problem - Time.png