Динамическое программирование резки стержня

Question

Учитывая стержень длиной n дюймов и массив цен, содержащий цены на все части размером меньше n. Используя динамическое программирование, мы можем получить максимальное значение и соответствующие части стержня. Есть ли какой-либо алгоритм, который будет давать k-е максимальное значение с соответствующим разрезом для этой проблемы?

Answer 1

Задача: Найти k th максимальная цена для проблемы с разрезом стержня.

Я думаю, что алгоритм может быть изменен следующим способом:

Изменения рекурсии в стержневых проблемах резки от:

cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1} 

To:

Top_K_Price_CutRod(n)[] = top_k(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1} 

В принципе, в каждой рекурсии step, return max k цены для этого подраздела, потому что только те могут быть в конечном итоге в общем максимуме k.

Bruteforce способ вернуть все возможные цены этого подраздела, но мы точно знаем, что цены, имеющие ранг больше k для этого подраздела, не могут быть в топ k цены на полный стержень в конце концов.

Таким образом, здесь Top_K_Price_CutRod(n)[] представляет собой массив из k максимальных цен для этого подраздела. В корне рекурсии вы останетесь с максимальными максимальными k ценами.

Я не думаю, что мы можем оптимизировать больше, чем это, так как на каждом узле рекурсии его верхнее значение k может быть среди окончательного верхнего k. Поэтому у вас должно быть k значений для всех подчастей.