LabASD - Il problema del resto greedy

Moreno Marzolla

Ultimo aggiornamento: 2023-04-20

Il problema del resto (change-making problem) è definito nel modo seguente: date \(t\) denominazioni (tagli) di monete o banconote \(T_0, \ldots, T_{t-1}\), in cui disponiamo di infiniti pezzi di ciascun taglio, determinare il minimo numero di pezzi da utilizzare per erogare un resto \(R\).

Nel caso dell’Euro, i tagli (espressi in centesimi) sono 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000 (da un centesimo fino a 500€). Il problema del resto può essere risolto usando una strategia greedy: si utilizza il massimo taglio minore o uguale al residuo da erogare. Se alla fine del procedimento il residuo è zero, il resto è erogabile e il numero di pezzi utilizzati è il minimo possibile.

Ad esempio, dovendo erogare un resto di \(R=96\) centesimi di Euro, l’algoritmo greedy utilizzerebbe pezzi da 50, 20, 20, 5, 1 per un totale di 5 pezzi, che è il minimo numero di pezzi considerando tutti i possibili tagli di euro a disposizione.

Sistemi monetari per i quali l’algoritmo greedy produce la soluzione ottima sono detti sistemi monetari canonici; l’euro, il dollaro USA e altri sono tutti sistemi monetari canonici.

In questo esercizio applichiamo l’algoritmo greedy ad un problema diverso, per il quale però l’algoritmo potrebbe non produrre la soluzione ottima, e potrebbe addirittura non trovare una soluzione anche quando questa esiste.

Il problema è il seguente: disponiamo di \(n\) monete (o banconote) di valori interi strettamente positivi \(m_0, \ldots, m_{n-1}\); i valori non sono necessariamente ordinati, e possono esistere più monete con lo stesso valore. Ogni moneta/banconota può essere usata al più una volta. Determinare il minimo numero di monete, tra quelle a disposizione, che è necessario usare per erogare un dato resto \(R \geq 0\).

Applichiamo l’algoritmo greedy nel modo seguente: ordiniamo le monete in ordine decrescente di valore, e consideriamo le monete una a una nella lista ordinata. Se il residuo da erogare è maggiore o uguale al valore della moneta che stiamo considerando, allora la usiamo, altrimenti la scartiamo e passiamo alla successiva.

Ad esempio, supponiamo di avere le monete seguenti (che per comodità vengono riportate già in ordine decrescente di valore):

50, 50, 20, 10, 10, 10, 5, 2, 1

e dobbiamo erogare l’importo \(R=96\). La Tabella 1 mostra il comportamento dell’algoritmo greedy: la colonna “Residuo” indica il resto ancora da erogare; la colonna “Moneta” indica il valore della moneta che stiamo considerando; infine, la colonna “Usata?” indica se usiamo la moneta o la scartiamo.

Tabella 1: Esempio di esecuzione dell’algoritmo greedy del resto
Residuo Moneta Usata?
96 50
46 50 no
46 20
26 10
16 10
6 10 no
6 5
1 2 no
1 1
0 stop

Quindi, l’algoritmo usa le sei monete di valore 50, 20, 10, 10, 5, 1.

Si noti che l’algoritmo di cui sopra potrebbe fallire in certi casi: ad esempio, se le monete a disposizione fossero \(5, 2, 2, 2, 2, 2\) e dovessimo erogare un resto \(R=10\), l’algoritmo utilizzerebbe la moneta di valore \(5\) e non sarebbe poi in grado di continuare, concludendo (erroneamente) che il resto non è erogabile. In realtà l’importo \(R=10\) può essere erogato usando le cinque monete da \(2\) 1.

Il programma legge i parametri di input da un file il cui nome va specificato sulla riga di comando. Il file ha il seguente formato:

R n
m[0]
...
m[n-1]

dove \(R\) indica il resto da erogare (intero maggiore o uguale a zero), \(n\) indica il numero di monete a disposizione (intero maggiore di zero), e m[0..n-1] sono i valori delle \(n\) monete a disposizione (interi maggiori di zero).

I valori delle monete non sono necessariamente ordinati. Per ordinarli si può usare un algoritmo di ordinamento (possibilmente efficiente) tra quelli visti a lezione, oppure si può usare la funzione qsort() dichiarata in <stdlib.h>, la cui segnatura è:

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
           int (*compare)(const void *, const void *));

dove:

Occorre prestare attenzione alla funzione di confronto: dovendo ordinare le monete in senso decrescente, la funzione di confronto deve restituire un valore negativo se il primo parametro è maggiore del secondo, un valore positivo se il primo parametro è minore del secondo, e zero se sono uguali.

Per compilare:

    gcc -std=c90 -Wall -Wpedantic resto-greedy.c -o resto-greedy

Per eseguire in ambiente Linux/MacOSX:

    ./resto-greedy resto-greedy.in

Per esguire in ambiente Windows:

    .\resto-greedy resto-greedy.in
Esempi
Input Output
13 8
20
20
20
10
5
2
1
1
Resto 13 erogabile con 3 monete:
10 2 1
27 4
50
1
5
20
Resto 27 non erogabile con le monete a disposizione
10 6
5
2
2
2
2
2
Resto 10 non erogabile con le monete a disposizione
(si noti che non sarebbe la soluzione corretta, perché il resto è erogabile usando le cinque monete di valore 2; è tuttavia la soluzione corretta calcolata dall’algoritmo greedy da implementare).

File


  1. La soluzione ottima può essere trovata usando un algoritmo più complesso basato sulla programmazione dinamica, che esula da questo esercizio. L’algoritmo basato su programmazione dinamica funziona anche con sistemi monetari non canonici.