LabASD - Rod cutting problem

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, quali lunghezze occorre tagliare per ottenere tale guadagno massimo.

Il programma legge l’input da un file il cui nome va specificato sulla riga di comando. Il file contiene \(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:

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(j)\) il sottoproblema che consiste nel determinare il massimo guadagno che si può ottenere suddividendo un’asta di lunghezza \(j\), \(j = 0, \ldots, n\). Denotiamo con \(r[j]\) la soluzione del problema \(P(j)\), cioè il guadagno massimo. Osserviamo che:

• \(r[0] = 0\), perché da un’asta di lunghezza zero non guadagniamo nulla;

• Se l’asta ha lunghezza \(j>0\), possiamo decidere di tagliare un segmento lungo \(i\) da rivendere al prezzo \(p[i]\), e suddividere in modo ottimo il residuo di lunghezza \((j-i)\) ottenendo un guadagno \(r[j-i]\). Per massimizzare il guadagno complessivo, scegliamo il valore \(i\) che massimizza il guadagno. Il guadagno massimo sarà quindi \(r[j] = \max_{1 \leq i \leq j} \{ p[i] + r[j-i] \}\)

In modo più compatto, possiamo scrivere:

\[ p[j] = \begin{cases} 0 & \mbox{se}\ j = 0\\ \displaystyle\max_{1 \leq i \leq j} \{ p[i] + r[j-i] \} & \mbox{altrimenti} \end{cases} \]

La soluzione al problema di partenza (massimo guadagno ottenibile suddividendo un tubo lungo \(n\)) è \(r[n]\).

Per conoscere la sequenza di tagli che produce il guadagno massimo \(r[n]\) è utile introdurre un array di supporto \(s[1], s[2], \ldots, s[n]\). Per ogni \(j = 1, \ldots, n\), \(s[j]\) è il valore di \(i\) che massimizza l’espressione \(p[i] + r[j-1]\) di cui sopra. Nell’esempio precedente si ha:

Da cui:

• Per ottenere il guadagno ottimo \(r[10]\) è stato asportato per ultimo un segmento lungo \(s[10] = 2\); il residuo ha lunghezza 8.

• Per ottenere il guadagno ottimo \(r[8]\) è stato asportato per ultimo un segmento lungo \(s[8] = 2\); il residuo ha lunghezza 6.

• Per ottenere il guadagno ottimo \(r[6]\) è stato asportato per ultimo un segmento lungo \(s[6] = 6\); il residuo ha lunghezza 0, e il procedimento termina.

Per compilare:

    gcc -std=c90 -Wall -Wpedantic cut-rod.c -o cut-rod

Per eseguire in ambiente Linux/MacOSX:

    ./cut-rod cut-rod1.in

Per eseguire in ambiente Windows:

    .\cut-rod cut-rod1.in

File

• cut-rod.c
• cut-rod1.in (output atteso)
• cut-rod2.in
• cut-rod3.in
• cut-rod4.in