Rod Cutting Problem

Q: Qual é a complexidade de tempo do problema do corte de hastes?

A tabela leva tempo O(n²) e memória O(n): o comprimento len tenta len primeiras peças, totalizando n(n+1)/2 tentativas. Sem respostas armazenadas, a recursão faz exatamente 2^n chamadas para uma barra de comprimento n, pois cada comprimento chama todos os comprimentos menores.

Q: Por que o corte de hastes é um problema da mochila ilimitada?

Considere cada comprimento de peça k como um item de peso k e valor prices[k-1] , com cópias ilimitadas, e a haste como uma mochila de capacidade n que deve ser preenchida exatamente. O melhor valor total dos itens é, então, o melhor preço para a haste.

Q: Como descobrir onde cortar a haste?

Armazene, para cada comprimento, a primeira peça k que proporcionou o melhor preço. Comece no comprimento n: corte uma peça do comprimento armazenado, passe para o comprimento que resta e repita até chegar a 0. As peças formam um plano ideal.

MédioProgramação dinâmica

+10

Você tem uma haste de comprimento n, em que n = prices.length. Um pedaço de comprimento k é vendido por prices[k-1]. Você pode cortar a haste em pedaços de comprimentos inteiros, quantos quiser, ou vendê-la inteira. Retorne o maior valor que você pode ganhar vendendo toda a haste.

Função

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] é o preço de uma peça de comprimento k; a barra tem comprimento prices.length
Retornainteger: o máximo de dinheiro que a vara inteira pode ganhar

Restrições

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

Exemplos

Entrada: prices = [2, 5, 7, 8]
Saída: 10
Explicação: Dois pedaços de comprimento 2 são vendidos por 5 + 5 = 10. Vender a barra inteira rende 8, e um pedaço de comprimento 1 mais um pedaço de comprimento 3 rendem 2 + 7 = 9.

Para ir além

E se você puder cortar a haste no máximo m vezes? O que cada entrada da tabela precisa saber nesse caso?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma barra de comprimento n pode ser cortada de 2^(n-1) maneiras. Você nunca precisa de todas elas: seja qual for a primeira peça, o restante é uma barra mais curta que faz a mesma pergunta. Portanto, existem apenas n+1 respostas, uma por comprimento, e calculá-las da menor para a maior leva O(n²) etapas.

Experimente todos os comprimentos para a primeira peça

Correta, mas não termina nos maiores testes

Intuição

Seja qual for o plano, a peça na extremidade esquerda tem algum comprimento k de 1 até o comprimento da haste e rende prices[k-1]; o restante do plano corta uma haste de comprimento length-k. Portanto, best(length) é 0 para comprimento 0 e, caso contrário, é o maior valor de prices[k-1] + best(length-k) para todos os k, em que k = length vende a haste inteira. Todo plano tem uma primeira peça, então esse máximo abrange todos os planos.

Cada chamada se ramifica em todos os comprimentos menores, então o número de chamadas dobra a cada unidade de comprimento: uma haste de 40 gera cerca de 2^40, ou 10^12, chamadas.

Algoritmo

Escreva best(length), que retorna 0 para o comprimento 0.
Para cada primeiro pedaço k de 1 até length, calcule prices[k-1] + best(length-k).
Retorne o maior desses valores.
Retorne 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))

Melhor preço para cada comprimento, começando pelo mais curto

Intuição

A recursão recalcula os mesmos valores: best(2) é solicitado por best(3), best(4) e por cada haste mais longa. Há apenas n+1 comprimentos, então calcule cada um uma única vez em um array best. Um comprimento lê apenas comprimentos menores, portanto preencher o array de 0 para cima significa que cada valor estará pronto quando for lido.

Em [2, 5, 7, 8]: best[1] é 2, best[2] é o maior entre 2 + 2 e 5, ou seja, 5, best[3] é 7, e best[4] é o maior entre 2 + 7, 5 + 5, 7 + 2 e 8, ou seja, 10.

Diferentemente da mochila 0/1, best[len-k] pode já conter peças de comprimento k, e é isso que você quer, já que um comprimento pode ser cortado quantas vezes você quiser. O comprimento len tenta primeiro peças de len: n(n+1)/2 passos no total, cerca de 5 × 10^5 para uma haste de 1000.

Algoritmo

Crie best com n + 1 entradas, todas 0.
Para cada length de 1 a n, tente cada primeiro pedaço k de 1 a length.
Calcule prices[k-1] + best[length-k] e mantenha o maior valor em best[length].
Retorne 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]

Armadilhas e casos extremos

Ler prices[k] para o comprimento k. Isso atribui a cada peça um preço como se ela fosse um tamanho maior e ultrapassa o fim em k = n; use prices[k-1].
Deixar de fora k = length, a peça sem cortes. Então best[1] permanece 0, e [1, 3, 8] resulta em 3 em vez de 8.
Cortar de forma gulosa com base no melhor preço por unidade. Em [2, 7, 11, 13], o comprimento 3 rende mais por unidade, mas 11 por essa peça mais 2 pelo restante totaliza 13, enquanto duas peças de comprimento 2 totalizam 14.
Usar memoização de cima para baixo em Python. A recursão ainda se aninha até a profundidade do comprimento da barra: uma barra de 1000 gera 1001 chamadas aninhadas, ultrapassando o limite padrão de 1000. Preencha o array de baixo para cima.

Perguntas frequentes4

Qual é a complexidade de tempo do problema do corte de hastes?

A tabela leva tempo O(n²) e memória O(n): o comprimento len tenta len primeiras peças, totalizando n(n+1)/2 tentativas. Sem respostas armazenadas, a recursão faz exatamente 2^n chamadas para uma barra de comprimento n, pois cada comprimento chama todos os comprimentos menores.

Por que o corte de hastes é um problema da mochila ilimitada?

Considere cada comprimento de peça k como um item de peso k e valor prices[k-1], com cópias ilimitadas, e a haste como uma mochila de capacidade n que deve ser preenchida exatamente. O melhor valor total dos itens é, então, o melhor preço para a haste.

Como descobrir onde cortar a haste?

Armazene, para cada comprimento, a primeira peça k que proporcionou o melhor preço. Comece no comprimento n: corte uma peça do comprimento armazenado, passe para o comprimento que resta e repita até chegar a 0. As peças formam um plano ideal.

Como a solução muda se cada corte custar dinheiro?

Vender a barra inteira não envolve nenhum corte, enquanto qualquer outra primeira peça adiciona um corte. Assim, best[len] se torna o maior valor entre prices[len-1] e o maior prices[k-1] + best[len-k] - cost para k menor que len. O restante da tabela permanece igual.

def cutRod(prices):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

prices = [2, 5, 7, 8]

Saída Esperada