The rod-cutting problem is the following. Given a rod of length n inches and a table of prices pi for i D 1;2; : : : ;n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces. Note that if the price pn for a rod of length n is large enough, an optimal solution may require no cutting at all.

int rodcuttin() {