Rod Cutting Problem

Q: Какова временная сложность задачи разрезания стержня?

Таблица требует времени O(n²) и памяти O(n): для длины len проверяются первые len отрезков, всего n(n+1)/2 проверок. Без сохранённых ответов рекурсия делает ровно 2^n вызовов для стержня длины n, поскольку для каждой длины вызываются все меньшие длины.

Q: Почему задача разрезания стержня — это задача о неограниченном рюкзаке?

Рассматривай длину каждого куска k как предмет с весом k и стоимостью prices[k-1] , которого можно взять неограниченное количество, а стержень — как рюкзак вместимостью n, который нужно заполнить полностью. Тогда наилучшая общая стоимость предметов будет равна наилучшей цене стержня.

Q: Как определить, где разрезать стержень?

Для каждой длины сохраните первую часть k , которая дала наилучшую цену. Начните с длины n: отрежьте часть сохранённой длины, перейдите к оставшейся длине и повторяйте, пока она не станет равна 0. Эти части составляют один оптимальный план.

СреднеДинамическое программирование

+10

У вас есть стержень длины n, где n = prices.length. Кусок длины k можно продать за prices[k-1]. Вы можете разрезать стержень на любое количество кусков целой длины или продать его целиком. Верните максимальную сумму, которую можно выручить, продав весь стержень.

Функция

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] — это цена куска длиной k; длина стержня равна prices.length
Возвращаетinteger: максимальная сумма, которую может принести весь стержень

Ограничения

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

Примеры

Ввод: prices = [2, 5, 7, 8]
Вывод: 10
Пояснение: Два куска длиной 2 продаются за 5 + 5 = 10. Продажа целого стержня приносит 8, а кусок длиной 1 и кусок длиной 3 приносят 2 + 7 = 9.

Дополнительный вопрос

Что, если ты можешь разрезать стержень не более m раз? Что тогда нужно знать о каждой ячейке таблицы?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Стержень длины n можно разрезать 2^(n-1) способами. Все они не нужны: какой бы ни была первая часть, остаток — это более короткий стержень, для которого нужно ответить на тот же вопрос. Поэтому существует всего n+1 ответов — по одному для каждой длины, а вычисление их, начиная с самой короткой, занимает O(n²) шагов.

Попробуйте все длины для первой детали

Верно, но не успевает на самых больших тестах

Идея

Каков бы ни был план, кусок на левом конце имеет длину k от 1 до длины стержня и приносит prices[k-1]; оставшаяся часть плана разрезает стержень длиной length-k. Поэтому best(length) равно 0 при длине 0, а в остальных случаях — наибольшему значению prices[k-1] + best(length-k) для всех k, где k = length означает, что стержень продаётся целиком. У каждого плана есть первый кусок, поэтому этот максимум охватывает все планы.

Каждый вызов разветвляется на все меньшие длины, поэтому число вызовов удваивается с каждой единицей длины: для стержня длиной 40 будет около 2^40, или 10^12, вызовов.

Алгоритм

Напишите best(length), которая возвращает 0 при длине 0.
Для каждого первого куска k от 1 до length вычислите prices[k-1] + best(length-k).
Верните наибольшее из этих значений.
Верните best(n).

def cutRod(prices):
    # The most money a rod of this length can earn
    def best(length):
        top = 0
        for piece in range(1, length + 1):
            # sell a first piece of this length, then cut the rest as well as possible
            top = max(top, prices[piece - 1] + best(length - piece))
        return top

    return best(len(prices))

Лучшая цена для любой длины, сначала самые короткие

Идея

Рекурсия повторно вычисляет одни и те же значения: best(2) запрашивается функциями best(3), best(4) и всеми функциями для более длинных стержней. Длин всего n+1, поэтому вычисли каждую один раз и сохрани в массиве best. Для длины нужны только меньшие длины, поэтому при заполнении массива от 0 вверх каждое значение будет готово к моменту чтения.

Для [2, 5, 7, 8]: best[1] равно 2, best[2] — большее из 2 + 2 и 5, то есть 5, best[3] равно 7, а best[4] — наибольшее из 2 + 7, 5 + 5, 7 + 2 и 8, то есть 10.

В отличие от задачи о рюкзаке 0/1, best[len-k] уже может содержать отрезки длины k, и именно это нужно, поскольку стержень можно резать сколько угодно раз. Длина len перебирает первые отрезки длины len: всего n(n+1)/2 шагов, около 5 × 10^5 для стержня длиной 1000.

Алгоритм

Создай best с n + 1 элементами, все равны 0.
Для каждого length от 1 до n попробуй каждую длину первого куска k от 1 до length.
Вычисли prices[k-1] + best[length-k] и сохрани наибольшее значение в best[length].
Верни best[n].

def cutRod(prices):
    n = len(prices)
    # best[length]: the most money a rod of that length can earn
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            # a first piece of this length, then the best for what is left
            earned = prices[piece - 1] + best[length - piece]
            if earned > best[length]:
                best[length] = earned
    return best[n]

Ловушки и крайние случаи

Обращение к prices[k] для длины k. Так цена каждой заготовки будет рассчитана для длины на единицу больше, а при k = n произойдёт выход за границы массива; используйте prices[k-1].
Пропуск k = length — неразрезанной заготовки. Тогда best[1] останется равным 0, а для [1, 3, 8] будет получена оценка 3 вместо 8.
Жадное разрезание по наибольшей цене за единицу длины. Для [2, 7, 11, 13] длина 3 даёт наибольшую цену за единицу, но 11 за неё плюс 2 за остаток дают 13, тогда как две заготовки длины 2 дают 14.
Мемоизация сверху вниз в Python. Вложенность рекурсии всё равно достигает длины стержня: для стержня длиной 1000 она составляет 1001 вызов, что превышает ограничение по умолчанию в 1000. Заполняйте массив снизу вверх.

Частые вопросы4

Какова временная сложность задачи разрезания стержня?

Таблица требует времени O(n²) и памяти O(n): для длины len проверяются первые len отрезков, всего n(n+1)/2 проверок. Без сохранённых ответов рекурсия делает ровно 2^n вызовов для стержня длины n, поскольку для каждой длины вызываются все меньшие длины.

Почему задача разрезания стержня — это задача о неограниченном рюкзаке?

Рассматривай длину каждого куска k как предмет с весом k и стоимостью prices[k-1], которого можно взять неограниченное количество, а стержень — как рюкзак вместимостью n, который нужно заполнить полностью. Тогда наилучшая общая стоимость предметов будет равна наилучшей цене стержня.

Как определить, где разрезать стержень?

Для каждой длины сохраните первую часть k, которая дала наилучшую цену. Начните с длины n: отрежьте часть сохранённой длины, перейдите к оставшейся длине и повторяйте, пока она не станет равна 0. Эти части составляют один оптимальный план.

Как изменится решение, если каждый разрез стоит денег?

Продажа стержня целиком не требует разреза, тогда как для любого другого первого куска нужен один разрез. Поэтому best[len] становится большим из prices[len-1] и наибольшего значения prices[k-1] + best[len-k] - cost для k, меньшего len. Остальная часть таблицы остается прежней.

def cutRod(prices):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

prices = [2, 5, 7, 8]

Ожидаемый вывод