Rod Cutting Problem

Q: Perché il taglio delle aste è un problema dello zaino illimitato?

Considera ogni pezzo di lunghezza k come un articolo di peso k e valore prices[k-1] , con copie illimitate, e l’asta come uno zaino di capacità n che deve essere riempito esattamente. Il valore totale migliore degli articoli è quindi il prezzo migliore per l’asta.

Q: Come fai a trovare il punto in cui tagliare l’asta?

Memorizza, per ogni lunghezza, il primo pezzo k che ha dato il prezzo migliore. Parti dalla lunghezza n: taglia un pezzo della lunghezza memorizzata, passa alla lunghezza rimanente e ripeti finché non raggiunge 0. I pezzi formano un piano ottimale.

MedioProgrammazione dinamica

+10

Hai un'asta di lunghezza n, dove n = prices.length. Un pezzo di lunghezza k si vende a prices[k-1]. Puoi tagliare l'asta in pezzi di lunghezze intere, quanti ne vuoi, oppure venderla in un unico pezzo. Restituisci la somma massima che puoi guadagnare vendendola tutta.

Funzione

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] è il prezzo di un pezzo di lunghezza k; la barra è lunga prices.length
Restituisceinteger: il massimo denaro che l’intera canna può guadagnare

Vincoli

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

Esempi

Input: prices = [2, 5, 7, 8]
Output: 10
Spiegazione: Due pezzi di lunghezza 2 si vendono a 5 + 5 = 10. Vendere l’asta intera frutta 8, mentre un pezzo di lunghezza 1 più un pezzo di lunghezza 3 fruttano 2 + 7 = 9.

Per approfondire

Che cosa succede se puoi tagliare l’asta al massimo m volte? Che cosa deve sapere allora ogni voce della tabella?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Una barra di lunghezza n può essere tagliata in 2^(n-1) modi. Non ti servono mai tutti: qualunque sia il primo pezzo, il resto è una barra più corta che pone la stessa domanda. Quindi esistono solo n+1 risposte, una per ogni lunghezza, e calcolarle dalla più corta alla più lunga richiede O(n²) passaggi.

Prova ogni lunghezza per il primo pezzo

Corretto, ma non termina sui test più grandi

Intuizione

Qualunque sia il piano, il pezzo all’estremità sinistra ha una lunghezza k compresa tra 1 e la lunghezza dell’asta e rende prices[k-1]; il resto del piano taglia un’asta di lunghezza length-k. Quindi best(length) è 0 per una lunghezza pari a 0 e, altrimenti, è il valore massimo di prices[k-1] + best(length-k) per tutti i valori di k, dove k = length significa vendere l’asta intera. Ogni piano ha un primo pezzo, quindi questo massimo comprende tutti i piani.

Ogni chiamata genera diramazioni per tutte le lunghezze minori, quindi il numero di chiamate raddoppia a ogni unità di lunghezza: un’asta di 40 genera circa 2^40, ovvero 10^12, chiamate.

Algoritmo

Scrivi best(length), che restituisce 0 per una lunghezza pari a 0.
Per ogni primo pezzo k da 1 a length, calcola prices[k-1] + best(length-k).
Restituisci il valore più grande tra questi.
Restituisci 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))

Il prezzo migliore per ogni lunghezza, dalla più corta alla più lunga

Intuizione

La ricorsione ricalcola gli stessi valori: best(2) viene richiesto da best(3), best(4) e da ogni asta più lunga. Ci sono solo n+1 lunghezze, quindi calcola ciascuna una sola volta in un array best. Una lunghezza legge solo lunghezze minori, quindi riempire l’array partendo da 0 fa sì che ogni valore sia pronto quando viene letto.

Con [2, 5, 7, 8]: best[1] è 2, best[2] è il maggiore tra 2 + 2 e 5, quindi 5, best[3] è 7 e best[4] è il massimo tra 2 + 7, 5 + 5, 7 + 2 e 8, quindi 10.

A differenza dello zaino 0/1, best[len-k] può già contenere pezzi di lunghezza k, ed è proprio quello che vuoi, poiché una lunghezza può essere tagliata tutte le volte che vuoi. La lunghezza len prova per prima cosa len pezzi: in tutto n(n+1)/2 passaggi, circa 5 × 10^5 per un’asta di 1000.

Algoritmo

Crea best con n + 1 elementi, tutti pari a 0.
Per ogni length da 1 a n, prova ogni primo pezzo k da 1 a length.
Calcola prices[k-1] + best[length-k] e mantieni il valore più grande in best[length].
Restituisci 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]

Trappole e casi limite

Leggere prices[k] per la lunghezza k. In questo modo si considera ogni pezzo più lungo di una misura e si va oltre la fine con k = n; usa prices[k-1].
Escludere k = length, il pezzo non tagliato. Così best[1] rimane 0 e [1, 3, 8] totalizza 3 invece di 8.
Tagliare in modo greedy scegliendo il prezzo migliore per unità. Con [2, 7, 11, 13], la lunghezza 3 rende di più per unità, ma 11 per quel pezzo più 2 per l'avanzo fanno 13, mentre due pezzi di lunghezza 2 fanno 14.
Memorizzare i risultati con un approccio top-down in Python. La ricorsione continua ad annidarsi fino a raggiungere la lunghezza dell'asta: un'asta di 1000 crea 1001 chiamate annidate, superando il limite predefinito di 1000. Riempi l'array dal basso verso l'alto.

Domande frequenti4

Qual è la complessità temporale del problema del taglio della barra?

La tabella richiede un tempo O(n²) e una memoria O(n): la lunghezza len prova len primi pezzi, per un totale di n(n+1)/2 tentativi. Senza risposte memorizzate, la ricorsione effettua esattamente 2^n chiamate per un’asta di lunghezza n, poiché ogni lunghezza chiama tutte le lunghezze inferiori.

Perché il taglio delle aste è un problema dello zaino illimitato?

Considera ogni pezzo di lunghezza k come un articolo di peso k e valore prices[k-1], con copie illimitate, e l’asta come uno zaino di capacità n che deve essere riempito esattamente. Il valore totale migliore degli articoli è quindi il prezzo migliore per l’asta.

Come fai a trovare il punto in cui tagliare l’asta?

Memorizza, per ogni lunghezza, il primo pezzo k che ha dato il prezzo migliore. Parti dalla lunghezza n: taglia un pezzo della lunghezza memorizzata, passa alla lunghezza rimanente e ripeti finché non raggiunge 0. I pezzi formano un piano ottimale.

Come cambia la soluzione se ogni taglio costa denaro?

Vendere l’asta intera non comporta alcun taglio, mentre ogni altro primo pezzo ne aggiunge uno. Quindi best[len] diventa il maggiore tra prices[len-1] e il massimo prices[k-1] + best[len-k] - cost per k minore di len. Il resto della tabella rimane invariato.

def cutRod(prices):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

prices = [2, 5, 7, 8]

Output atteso