Esercizio 15ordini con scadenza e profitto massimo

In questa pagina 5

Testo (scritto del 16/06/2025, seconda parte, esercizio 2, 6 punti). Gestisci un'azienda che produce circuiti elettronici customizzati. Hai una serie di ordini, ciascuno caratterizzato da tre parametri: id, scadenza (in giorni) e profitto. Ogni circuito richiede un giorno per essere completato. Gli ordini che hai sono troppi per riuscire a rispettare tutte le scadenze: devi quindi rinunciare ad alcuni ordini. Vuoi però tenere quelli che ti garantiscono il maggior profitto, rispettando al tempo stesso le scadenze. Istanza di esempio (id: scadenza, profitto):

$(1: 4, 70)$ , $(2: 2, 60)$ , $(3: 4, 50)$ , $(4: 3, 40)$ , $(5: 1, 30)$ , $(6: 4, 20)$ , $(7: 6, 90)$ , $(8: 2, 10)$ , $(9: 3, 80)$ , $(10: 1, 20)$ , $(11: 5, 100)$ , $(12: 6, 30)$ , $(13: 2, 55)$ , $(14: 5, 35)$ , $(15: 3, 25)$ .

Gli ordini con scadenza $1$ vanno consegnati domani, quelli con scadenza $2$ dopodomani e così via. In sei giorni, però, potrai produrre e consegnare solo $6$ circuiti, uno al giorno. Quali sono i $6$ ordini che ti garantiscono il maggior profitto rispettando le scadenze? (Di quelli con scadenza $1$ potrai sceglierne al massimo $1$ , di quelli con scadenza $2$ al massimo $2$ sacrificando quelli con scadenza $1$ se poco redditizi, e così via.) Descrivere un algoritmo iterativo in pseudocodice che, data una qualsiasi lista di ordini, restituisca la lista di ordini che garantiscono il maggior profitto rispettando le scadenze. Il punteggio pieno si otterrà con un algoritmo di complessità al caso pessimo $\in O(n \log n)$ . Consigli: si può assumere la lista ordinata per scadenza; usare una coda con priorità con il profitto come chiave; scegliere tra coda sul minimo o sul massimo.

(a) Descrivere a parole l'idea, con l'istanza di esempio. (b) Specificare firma, input e output. (c) Scrivere l'algoritmo in pseudocodice. (d) Analizzare la complessità al caso pessimo scegliendo una implementazione della coda con priorità.

(a) Idea

Un insieme $S$ di ordini è realizzabile se per ogni $t \ge 1$ il numero di ordini di $S$ con scadenza $\le t$ è al più $t$ (in $t$ giorni si producono al più $t$ circuiti). Si scorrono gli ordini per scadenza crescente tenendo l'insieme $S$ dei migliori finora, in una coda con priorità sul minimo (chiave = profitto): per ogni nuovo ordine con scadenza $d$ lo si inserisce; se ora $\lvert S \rvert > d$ la scadenza non è rispettabile, e si elimina l'ordine meno redditizio (removeMin) tra quelli in $S$ , compreso il nuovo.

Perché la coda sul minimo: serve estrarre il profitto più basso, non il più alto. Perché funziona: gli ordini sono visti per scadenza crescente, quindi il nuovo ordine ha scadenza $\ge$ tutti quelli in $S$ e l'unico vincolo che può essere violato è $\lvert S \rvert \le d$ . Quando succede, togliere l'ordine di profitto minimo lascia un insieme realizzabile e di profitto massimo tra quelli di quella taglia (scambiando un ordine scelto con uno non scelto più redditizio non peggiora il risultato).

Traccia sull'istanza (ordinata per scadenza, scritti i profitti nello heap; dopo l'elaborazione di ciascun ordine):

Ordine $(d, p)$	Heap dopo inserimento	$\lvert S \rvert$ vs $d$	Azione	Heap finale del passo
$5$ : $(1, 30)$	$\{30\}$	$1 \le 1$	—	$\{30\}$
$10$ : $(1, 20)$	$\{20, 30\}$	$2 > 1$	togli $20$	$\{30\}$
$2$ : $(2, 60)$	$\{30, 60\}$	$2 \le 2$	—	$\{30, 60\}$
$8$ : $(2, 10)$	$\{10, 30, 60\}$	$3 > 2$	togli $10$	$\{30, 60\}$
$13$ : $(2, 55)$	$\{30, 55, 60\}$	$3 > 2$	togli $30$	$\{55, 60\}$
$4$ : $(3, 40)$	$\{40, 55, 60\}$	$3 \le 3$	—	$\{40, 55, 60\}$
$9$ : $(3, 80)$	$\{40, 55, 60, 80\}$	$4 > 3$	togli $40$	$\{55, 60, 80\}$
$15$ : $(3, 25)$	$\{25, 55, 60, 80\}$	$4 > 3$	togli $25$	$\{55, 60, 80\}$
$1$ : $(4, 70)$	$\{55, 60, 70, 80\}$	$4 \le 4$	—	$\{55, 60, 70, 80\}$
$3$ : $(4, 50)$	$+ 50$	$5 > 4$	togli $50$	$\{55, 60, 70, 80\}$
$6$ : $(4, 20)$	$+ 20$	$5 > 4$	togli $20$	$\{55, 60, 70, 80\}$
$11$ : $(5, 100)$	$\{55, 60, 70, 80, 100\}$	$5 \le 5$	—	$\{55, 60, 70, 80, 100\}$
$14$ : $(5, 35)$	$+ 35$	$6 > 5$	togli $35$	invariato
$7$ : $(6, 90)$	$\{55, 60, 70, 80, 90, 100\}$	$6 \le 6$	—	$\{55, 60, 70, 80, 90, 100\}$
$12$ : $(6, 30)$	$+ 30$	$7 > 6$	togli $30$	invariato

Risultato: gli ordini $13, 2, 1, 9, 11, 7$ con profitto totale $55 + 60 + 70 + 80 + 100 + 90 = \mathbf{455}$ . Un calendario valido: giorno $1$ : ordine $13$ ; giorno $2$ : ordine $2$ ; giorno $3$ : $9$ ; giorno $4$ : $1$ ; giorno $5$ : $11$ ; giorno $6$ : $7$ (ciascuno entro la sua scadenza). Il valore $455$ coincide con il massimo ottenuto provando tutti i $2^{15}$ sottoinsiemi (controllato con un programma, e l'algoritmo è stato confrontato con la ricerca esaustiva su istanze casuali).

(b) Firma

Algoritmo ordiniMigliori(ordini, n)
Input: array ordini[1..n]; ogni ordine ha id, scadenza (intero >= 1), profitto
Output: lista degli ordini scelti (realizzabili e di profitto massimo)

(c) Pseudocodice

ordina ordini per scadenza crescente
Q <- coda con priorità sul minimo, vuota          (chiave = profitto, valore = ordine)
for each o in ordini (nell'ordine) do
    Q.insert(o.profitto, o)
    if Q.size() > o.scadenza then
        Q.removeMin()                              (l'ordine meno redditizio tra quelli tenuti)
return la lista dei valori in Q

(d) Complessità

Ordinamento per scadenza: $O(n \log n)$ (oppure $\Theta(n + D)$ con un array di contatori se le scadenze sono interi in $[1, D]$ ).
Il ciclo ha $n$ iterazioni, ciascuna con un insert e al più un removeMin. Con uno heap (vedi Heap) ognuno costa $\Theta(\log n)$ (la dimensione dello heap è al più $\min(n, D)$ ): $O(n \log n)$ in totale.

Complessità totale $O(n \log n)$ al caso pessimo. Con una coda su lista non ordinata ogni removeMin costerebbe $\Theta(n)$ : $O(n^2)$ (vedi Code con priorità); con lista ordinata gli insert costerebbero $\Theta(n)$ : ancora $O(n^2)$ .

Errori comuni

Usare una coda sul massimo: si estrarrebbe l'ordine più redditizio, cioè proprio quello da tenere.
Scorrere gli ordini per scadenza decrescente o senza ordine: il controllo $\lvert S \rvert > d$ perde di significato.
Confrontare con la scadenza il numero di giorni trascorsi invece della dimensione dell'insieme tenuto.
Scegliere i $6$ ordini di profitto massimo ignorando le scadenze (nell'esempio: $100, 90, 80, 70, 60, 55$ sono proprio quelli giusti, ma solo perché le scadenze lo permettono; in generale non basta).

Versione ripasso

Testo. Ordini (id, scadenza, profitto), un circuito al giorno; scegliere gli ordini che rispettano le scadenze con profitto massimo, in $O(n \log n)$ , usando una coda con priorità (sul minimo o sul massimo?).

Realizzabile: per ogni $t$ , ordini con scadenza $\le t$ al più $t$ .
Idea: ordini per scadenza crescente; insert del profitto in una coda sul minimo; se $\text{size} > d$ allora removeMin (si scarta il meno redditizio). Perché il minimo: si scarta il profitto più basso (vedi Code con priorità).
Esempio: restano gli ordini $13, 2, 1, 9, 11, 7$ , profitto $55+60+70+80+100+90 = 455$ (uguale al massimo esaustivo).
Pseudocodice: ordina per scadenza; per ogni $o$ : Q.insert(o.profitto, o); se Q.size() > o.scadenza allora Q.removeMin(); restituisce $Q$ .
Complessità: ordinamento $O(n \log n)$ + $n$ iterazioni con insert e removeMin su heap $\Theta(\log n)$ (vedi Heap): $O(n \log n)$ ; con liste $O(n^2)$ .
Insieme realizzabile: per ogni $t$ , al più $t$ ordini con scadenza $\le t$ . Perché la coda sul minimo: si scarta l'ordine meno redditizio, quindi serve removeMin sul profitto.
Traccia sull'istanza: dopo $(1,30)$ , $(1,20)$ : resta $\{30\}$ ; dopo i tre ordini di scadenza $2$ : $\{55, 60\}$ ; scadenza $3$ : $\{55, 60, 80\}$ ; scadenza $4$ : $\{55, 60, 70, 80\}$ ; scadenza $5$ : $+100$ ; scadenza $6$ : $+90$ ⇒ ordini $13, 2, 1, 9, 11, 7$ .
Calendario: giorno 1: ordine $13$ ; 2: $2$ ; 3: $9$ ; 4: $1$ ; 5: $11$ ; 6: $7$ ; profitto $455$ (uguale all'ottimo esaustivo).
Alternative: con coda su lista non ordinata ogni removeMin costa $\Theta(n)$ ⇒ $O(n^2)$ ; con scadenze intere in $[1, D]$ l'ordinamento si fa in $\Theta(n + D)$ . Firma: ordiniMigliori(ordini, n) restituisce la lista degli ordini scelti.
Errori: coda sul massimo; scadenze non ordinate; profitti più alti senza controllare le scadenze.