The rod cutting problem is a classic problem in combinatorial optimization. There is a rod with a length of N units. This rod can be cut into several pieces with length smaller than N. Here, the prices of all pieces are given. The problem is to determine the maximum revenue obtainable by cutting up the rod and selling the pieces. Figure 1 shows an example of a rod with a length of 4 and the total revenues corresponding to the possible combinations of cutting up the rod. In this case, the value of an optimal solution (maximum revenue) is 13, and the sizes of the pieces for an optimal solution to cut off are 1 and 3.

The rod cutting problem - ITPEC FE 2017S - Notes