LabASD - Rod cutting problem

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-23

Disponiamo di un'asta di lunghezza intera \(n\), \(1 \leq n < N\), che possiamo tagliare in segmenti più corti da rivendere a prezzi diversi. Le lunghezze ammesse sono \(1, 2, \ldots, n\), e si vendono rispettivamente al prezzo \(p_1, p_2, \ldots, p_n\) (valori reali). Vogliamo determinare il massimo guadagno che è possibile ottenere dal taglio dell'asta; vogliamo inoltre determinare quali lunghezze occorre tagliare per ottenere tale guadagno massimo.

Il programma legge l'input da un file contenente gli \(n\) prezzi, uno per riga:

p1
p2
...
pn

Ad esempio, il file cut-rod1.in contiene i prezzi di dieci segmenti (\(n=10\)) come segue:

Lunghezza \(i\) 1 2 3 4 5 6 7 8 9 10
Prezzo \(p[i]\) 1 5 8 9 13 17 17 20 24 25

In questo caso la soluzione ottima consiste nel dividere l'asta lunga \(n=10\) in tre segmenti di lunghezze \(2+2+6\), ottenendo un guadagno \(5+5+17=27\).

Per risolvere efficientemente il problema si può usare la programmazione dinamica. Sia \(P(i)\) il sottoproblema che consiste nel determinare il massimo guadagno che si può ottenere suddividendo un'asta di lunghezza \(i\), \(0 \leq i \leq n\). Denotiamo con \(r[i]\) la soluzione del problema \(P(i)\), cioè il guadagno massimo. Osserviamo che:

File