/****************************************************************************
*
* resto-greedy.c -- Il problema del resto greedy
*
* Copyright (C) 2021, 2022, 2023 Moreno Marzolla
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*
****************************************************************************/
/***
% LabASD - Il problema del resto _greedy_
% Moreno Marzolla
% Ultimo aggiornamento: 2023-04-20
![](Euro_coins_and_banknotes.jpg "Euro in monete e banconote")
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](https://arxiv.org/pdf/0809.0400); 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 sì
46 50 no
46 20 sì
26 10 sì
16 10 sì
6 10 no
6 5 sì
1 2 no
1 1 sì
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].
[^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.
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 ``, la cui segnatura è:
```C
#include
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.
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 |Resto 13 erogabile con 3 monete: |
|20 |10 2 1 |
|20 |``` |
|20 | |
|10 | |
|5 | |
|2 | |
|1 | |
|1 | |
|``` | |
+---------+------------------------------------------------------+
|``` |``` |
|27 4 |Resto 27 non erogabile con le monete a disposizione |
|50 |``` |
|1 | |
|5 | |
|20 | |
|``` | |
+---------+------------------------------------------------------+
|``` |``` |
|10 6 |Resto 10 non erogabile con le monete a disposizione |
|5 |``` |
|2 |(si noti che non sarebbe la soluzione corretta, |
|2 |perché il resto è erogabile usando le cinque monete |
|2 |di valore 2; è tuttavia la soluzione corretta |
|2 |calcolata dall'algoritmo greedy da implementare). |
|2 | |
|``` | |
+---------+------------------------------------------------------+
## File
- [resto-greedy.c](resto-greedy.c)
- [resto-greedy.in](resto-greedy.in) ([risultato atteso](resto-greedy.out))
- [resto-greedy1.in](resto-greedy1.in)
- [resto-greedy2.in](resto-greedy2.in)
- [resto-greedy3.in](resto-greedy3.in)
- [resto-greedy4.in](resto-greedy4.in)
***/
#include
#include
#include
#include
/* Dobbiamo ordinare le monete in senso DECRESCENTE, quindi questa
funzione deve restituire un valore negativo se m1 > m2 */
int confronta_monete(const void *m1, const void *m2)
{
const int v1 = *(const int*)m1;
const int v2 = *(const int*)m2;
if (v1 > v2)
return -1;
else if (v1 < v2)
return 1;
else
return 0;
}
/* Date n monete i cui valori sono memorizzati nell'array m[] (non
necessariamente ordinato), restituisce il minimo numero di pezzi
necessari per erogare un resto R. Se il resto non è erogabile
restituisce -1. La funzione deve anche stampare quali monete usare,
in caso di resto erogabile, oppure un opportuno messaggio che
avvisa che il resto non è erogabile. */
int resto(int R, int m[], int n)
{
int *use = (int*)malloc(n * sizeof(*use));
int n_coins = 0; /* numero di monete utilizzate */
int i = 0;
int da_erogare = R;
assert(use != NULL);
/* ordiniamo le monete in senso decrescente */
qsort(m, n, sizeof(*m), confronta_monete);
for (i=0; i= m[i]) {
da_erogare -= m[i];
use[i] = 1;
n_coins++;
}
}
if (da_erogare > 0) {
printf("Resto %d non erogabile con le monete a disposizione\n", R);
n_coins = -1;
} else {
int n_printed = 0; /* come ulteriore controllo, non richiesto
dall'esercizio, assicuriamoci che il
numero di monete stampate sia
esattamente uguale a `n_coins` */
printf("Resto %d erogabile con %d monete:\n", R, n_coins);
for (i=0; i