LabASD - Il problema del resto

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-15

Disponiamo di \(n\) monete di valori interi rispettivamente \(m_0, \ldots, m_{n-1}\). Supponiamo che le monete appartengano ad un sistema monetario canonico, cioè un sistema monetario per il quale l'algoritmo greedy che descriviamo a breve produce la soluzione ottima. Dobbiamo erogare un resto \(R\) usando il minor numero possibile di monete. Scrivere un programma che determina se ciò è possibile, e in caso affermativo elenca quali monete fanno parte della soluzione ottima. Ogni moneta può essere usata al massimo una volta, ma possono essere presenti più monete con lo stesso valore.

Per i sistemi monetari canonici esiste un semplice algoritmo greedy, che consiste nel considerare le monete in ordine decrescente di valore. Se il resto ancora da erogare è maggiore o uguale al valore della moneta, allora la usiamo, altrimenti la scartiamo e passiamo alla moneta successiva.

Supponiamo ad esempio di disporre delle nove monete seguenti:

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

e vogliamo erogare un resto \(R=86\). La tabella seguente 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.

Esempio problema del resto
Residuo Moneta Usata?
86 50
36 50 no
36 20
16 10
6 10 no
6 10 no
6 5
1 2 no
1 1
0

Quindi, il numero minimo di monete necessarie per erogare il resto è 5.

Il programma legge i parametri di input dallo standard input o da file secondo il formato seguente:

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

I valori delle monete non sono necessariamente ordinati. Per ordinarli si può usare un qualunque algoritmo di ordinamento efficiente visto a lezione, oppure si può usare la funzione qsort() dichiarata nell'header file <stdlib.h>. La segnatura della funzione è la seguente:

#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. Dobbiamo infatti ordinare le monete in senso decrescente di valore; di conseguenza, 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.

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

File