LabASD - Il problema del resto limitato greedy

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; quasi tutti i sistemi monetari in uso sono canonici.

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

Il problema del resto limitato è 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 supponiamo di dover 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.

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

L’algoritmo greedy 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 da \(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\) ¹.

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\) è 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 strettamente maggiori di zero).

I valori delle monete non sono necessariamente ordinati. Per ordinarli si può usare un algoritmo di ordinamento 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:

• base è un puntatore all’inizio dell’array da ordinare;

• nmemb è il numero di elementi dell’array da ordinare (attenzione, non il numero di byte!)

• size è la dimensione in byte di ciascuno degli elementi dell’array

• compare è un puntatore ad una funzione del tipo int cmp(const void *a, const void *b) che restituisce:

  • un valore negativo, se a viene prima di b nell’ordinamento;

  • zero, se a e b sono considerati uguali;

  • un valore positivo, se a viene dopo b nell’ordinamento

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. Abbiamo già discusso l’uso della funzione qsort() in un altro esercizio.

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

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

File

• resto-greedy.c
• resto-greedy.in (risultato atteso)
• resto-greedy1.in
• resto-greedy2.in
• resto-greedy3.in
• resto-greedy4.in