Rod cutting problem (RCP)

Catalogue of combinatorial problems · Miscellaneous problems · Catalogue (PDF)

Definition 1: Rod cutting problem

Given:

1. a rod of length \(n \in \Z_{\ge 1}\),

2. a set \(\{1,2,\dots,n\}\) of \(n\) possible piece lengths,

3. for each piece length \(\ell \in \{1,2,\dots,n\}\), a profit \(p_\ell \in \Z_{\ge 1}\),

the Rod Cutting Problem (RCP) asks to decide how many copies of each piece length to cut, so that the total length of the obtained pieces is equal to the rod length, and the total profit of the obtained pieces is maximized.

What the course does on this problem

Technique	Where
Definition	This page
Dynamic programming	Ch. 16 «Principles of dynamic programming»; Ch. 28 «DP for the rod cutting problem»
Exercises	Ch. 28 (5 exercises)