Template Function ADS::rodCutting

• Defined in File KnapsackVariants.h

Function Documentation

template<class T>
std::pair<T, std::vector<std::size_t>> ADS::rodCutting(const std::vector<T> &price, std::size_t L)

the largest gain of a rod of length L cut in pieces of lengths 1 .

|price|, price[ t - 1 ] the price of a piece of length t, and the lengths of the pieces

Pre:

L = 0 or price not empty

Post:

the pieces sum to L and their prices to the gain