Rod Cutting Problem

Q: ¿Cuál es la complejidad temporal del problema de corte de varillas?

La tabla tarda O(n²) y usa O(n) de memoria: la longitud len prueba len primeras piezas; en total, n(n+1)/2 intentos. Sin respuestas almacenadas, la recursión realiza exactamente 2^n llamadas para una varilla de longitud n, ya que cada longitud llama a todas las longitudes menores.

Q: ¿Por qué el problema del corte de varillas es un problema de mochila ilimitada?

Considera cada longitud de pieza k como un elemento de peso k y valor prices[k-1] , con copias ilimitadas, y la varilla como una mochila de capacidad n que debe llenarse exactamente. El mejor valor total de los elementos es entonces el mejor precio para la varilla.

Q: ¿Cómo encuentras dónde cortar la varilla?

Almacena, para cada longitud, la primera pieza k que dio su mejor precio. Empieza en la longitud n: corta una pieza de la longitud almacenada, pasa a la longitud restante y repite hasta llegar a 0. Las piezas forman un plan óptimo.

MedioProgramación dinámica

+10

Tienes una varilla de longitud n, donde n = prices.length. Una pieza de longitud k se vende por prices[k-1]. Puedes cortar la varilla en tantas piezas de longitudes enteras como quieras, o venderla de una sola pieza. Devuelve la mayor cantidad de dinero que puedes ganar al venderla entera.

Función

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] es el precio de una pieza de longitud k; la varilla tiene una longitud de prices.length
Devuelveinteger: la mayor cantidad de dinero que puede ganar toda la caña

Restricciones

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

Ejemplos

Entrada: prices = [2, 5, 7, 8]
Salida: 10
Explicación: Dos piezas de longitud 2 se venden por 5 + 5 = 10. Vender la varilla entera genera 8, y una pieza de 1 más una pieza de 3 genera 2 + 7 = 9.

Para ir más allá

¿Y si puedes cortar la varilla como máximo m veces? ¿Qué necesita saber entonces cada entrada de la tabla?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una varilla de longitud n tiene 2^(n-1) maneras de cortarse. Nunca las necesitas todas: sea cual sea la primera pieza, el resto es una varilla más corta que plantea la misma pregunta. Así que solo existen n+1 respuestas, una por cada longitud, y calcularlas desde la más corta hacia arriba lleva O(n²) pasos.

Prueba todas las longitudes para la primera pieza

Correcto, pero no termina con las pruebas más grandes

Intuición

Sea cual sea el plan, la pieza del extremo izquierdo tiene una longitud k entre 1 y la longitud de la varilla, y genera prices[k-1]; el resto del plan corta una varilla de longitud length-k. Así que best(length) es 0 para una longitud 0 y, de lo contrario, el mayor valor de prices[k-1] + best(length-k) para todos los valores de k, donde k = length vende la varilla entera. Todo plan tiene una primera pieza, así que este máximo abarca todos los planes.

Cada llamada se ramifica en todas las longitudes menores, por lo que el número de llamadas se duplica con cada unidad de longitud: una varilla de 40 genera alrededor de 2^40, o 10^12, llamadas.

Algoritmo

Escribe best(length), que devuelve 0 para la longitud 0.
Para cada primera pieza k desde 1 hasta length, calcula prices[k-1] + best(length-k).
Devuelve el mayor de esos valores.
Devuelve 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))

Mejor precio para cada longitud, de menor a mayor

Intuición

La recursión vuelve a calcular los mismos valores: best(2) es solicitado por best(3), best(4) y cada segmento más largo. Solo hay n+1 longitudes, así que calcula cada una una sola vez en un array best. Una longitud solo lee longitudes más cortas, así que rellenar el array de 0 hacia arriba significa que cada valor está listo cuando se lee.

Con [2, 5, 7, 8]: best[1] es 2, best[2] es el mayor de 2 + 2 y 5, es decir, 5, best[3] es 7 y best[4] es el mayor de 2 + 7, 5 + 5, 7 + 2 y 8, es decir, 10.

A diferencia de la mochila 0/1, best[len-k] puede contener ya piezas de longitud k, y eso es lo que quieres, ya que una longitud se puede cortar tantas veces como quieras. La longitud len prueba primero len piezas: n(n+1)/2 pasos en total, aproximadamente 5 × 10^5 para una varilla de 1000.

Algoritmo

Crea best con n + 1 entradas, todas en 0.
Para cada length de 1 a n, prueba cada primera pieza k de 1 a length.
Calcula prices[k-1] + best[length-k] y guarda el valor más grande en best[length].
Devuelve 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]

Errores comunes y casos límite

Leer prices[k] para la longitud k. Así, se asigna a cada pieza el precio de una longitud mayor en una unidad y se sobrepasa el final en k = n; usa prices[k-1].
Omitir k = length, la pieza sin cortar. Entonces best[1] se queda en 0, y [1, 3, 8] obtiene una puntuación de 3 en lugar de 8.
Cortar de forma voraz según el mejor precio por unidad. Con [2, 7, 11, 13], la longitud 3 da el mayor precio por unidad, pero 11 por esa pieza más 2 por el sobrante suman 13, mientras que dos piezas de longitud 2 suman 14.
Usar memoización descendente en Python. La recursión sigue anidándose hasta alcanzar la longitud de la varilla: una varilla de 1000 genera 1001 llamadas anidadas, por encima del límite predeterminado de 1000. Rellena el arreglo de abajo arriba.

Preguntas frecuentes4

¿Cuál es la complejidad temporal del problema de corte de varillas?

La tabla tarda O(n²) y usa O(n) de memoria: la longitud len prueba len primeras piezas; en total, n(n+1)/2 intentos. Sin respuestas almacenadas, la recursión realiza exactamente 2^n llamadas para una varilla de longitud n, ya que cada longitud llama a todas las longitudes menores.

¿Por qué el problema del corte de varillas es un problema de mochila ilimitada?

Considera cada longitud de pieza k como un elemento de peso k y valor prices[k-1], con copias ilimitadas, y la varilla como una mochila de capacidad n que debe llenarse exactamente. El mejor valor total de los elementos es entonces el mejor precio para la varilla.

¿Cómo encuentras dónde cortar la varilla?

Almacena, para cada longitud, la primera pieza k que dio su mejor precio. Empieza en la longitud n: corta una pieza de la longitud almacenada, pasa a la longitud restante y repite hasta llegar a 0. Las piezas forman un plan óptimo.

¿Cómo cambia la solución si cada corte cuesta dinero?

Vender la varilla entera no implica ningún corte, mientras que cualquier otra primera pieza añade un corte. Así, best[len] pasa a ser el mayor valor entre prices[len-1] y el mayor prices[k-1] + best[len-k] - cost para k menor que len. El resto de la tabla permanece igual.

def cutRod(prices):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

prices = [2, 5, 7, 8]

Salida Esperada