Ancora su programmazione dinamica: il problema del resto¶

A cura di Claudio Busatto

Il cosiddetto “problema del cassiere” è un problema per qualsiasi persona si trovi a dover dividere un certo valore nel minor numero di monete/banconote. Questo problema può essere esteso a distributori automatici, bancomat, ecc..

In questo lavoro verrà approfondito tale compito e verrà analizzato l’algoritmo che affronta e risolve il problema nella maniera corretta e più efficiente possibile.

Siano x il valore relativo all’ammontare del resto e C = [c₁ , .., c_n ] il vettore di lunghezza n contenente il valore delle monete/banconote a disposizione. L’ipotesi è quella di avere a disposizione un numero infinito, o sufficientemente grande, di ogni elemento di C. L’output dell’algoritmo è un oggetto di tipo int relativo al minor numero di monete necessarie per pagare x. Se l’ammontare del resto non è raggiungibile con nessuna combinazione delle monete a disposizione l’algoritmo ritorna il valore Inf.

Il metodo più intuitivo per risolvere il problema in questione è un’algoritmo di tipo greedy che, ad ogni iterazione, seleziona la moneta con il massimo valore che non eccede la quantità residua da pagare e somma il numero di monete scelte. Tuttavia, nonostante l’idea possa sembrare buona e l’algoritmo richieda un basso numero di iterazioni, è facile dimostrare che la soluzione a cui converge l’algoritmo non è sempre corretta. Un algoritmo corretto ed efficiente per la risoluzione di tale problema si basa su un approccio di tipo dinamico. Le tecniche di programmazione dinamica sono utili quando il problema da risolvere può essere diviso in diversi sotto-problemi non indipendenti. In questo modo il problema si riduce alla ricerca delle soluzioni ottimali per i sotto-problemi e, successivamente, alla combinazione di queste per ottenere la soluzione ottimale al problema originale.

Nel problema del resto i sotto-problemi sono rappresentati dal minor numero di monete necessarie per pagare tutti i valori minori di x e le soluzioni vengono combinate volta per volta. Sia la funzione MinNum(int x) definita come

\[\begin{split}MinNum(i) = \left\{\begin{aligned} & 0 & \text{if } \; i = 0, \\ & \infty & \text{if } \; c_j > i \text{,} \; j = 1, .., n,\\ & 1+min_{j : c_j \le i}{MinNum(i - c_j)} & \text{altrimenti}. \\ \end{aligned}\right.\end{split}\]

Partendo da i = 0, ad ogni iterazione i viene applicata la funzione MinNum(i). Per ogni c_j , j = 1, .., n, viene valutato il numero di monete necessarie a pagare l’ammontare i - c_j e viene scelta la moneta per la quale tale numero è minimo, assicurando che i - c_j venga pagato usando il numero minimo di monete/banconote. A questo punto è sufficiente aggiungere una moneta c_j al set di monete da utilizzare per pagare i. Se non si ha a disposizione nessuna moneta con valore minore o uguale di i la funzione ritorna il valore Inf. Le soluzioni ottimali per ogni MinNum(i), i = 0, .., x-1, vengono salvate in un vettore di lunghezza x, cosi da non doverle ricalcolare ogni volta.

# ::::::::::::::::::::::::::::::::::::::::
# Coin Changing Algorithm

def Min_Number_Coin(x, C):
  # x value to be paid
  # C values of different available coins

  # ::::::::::::::::::::::::::::::::::::::::
  # initialization

  # n length of vector C, MN output vector
  n = len(C)
  MN = [0 for i in range(x+1)]

  # ::::::::::::::::::::::::::::::::::::::::
  # main cycle

  for i in range(1, x+1):

      # set to Inf in case there is no valid combination
      MN[i] = float("Inf")

              # check MinNum(i) for every j
      for j in range(0, n):
         if C[j] <= i and MN[i] > 1 + MN[i - C[j]] :
              MN[i] =  1 + MN[i - C[j]]

  # ::::::::::::::::::::::::::::::::::::::::
  # output

  return MN[x]

Per esempio, si supponga di dover pagare un resto x = 123 avendo a disposizione un set di monete/banconote C = [1, 2, 5, 10, 20, 50]. L’output dell’algoritmo è out = 5, corretto, in quanto il la soluzione è 123 = 50 + 50 + 20 + 2 + 1. Se fosse di interesse il set di monete ottimale, è sufficiente salvare in un vettore le monete c_j selezionate: ad ogni iterazione, una volta selezionata la moneta ottimale c_j che soddisfa la funzione MinNum(i), viene richiamato il vettore relativo al set di monete ottimale necessarie per pagare i - c_j e a questo viene aggiunta la moneta c_j necessaria a raggiungere il valore i.

Complessità computazionale¶

Il costo computazionale dell’algoritmo è pseudo-polinomiale, in quanto sono necessari due cicli. Il primo ciclo è relativo alle iterazioni i = 0, .., x e, per ognuna di queste, un ulteriore ciclo di j = 1, .., n iterazioni è necessario per applicare e valutare la funzione MinNum(i). Il costo computazionale asintotico si può riassumere come O(nx). Se fosse di interesse anche l’effettivo set di monete, il costo asintotico non cambia, tuttavia i costi di memoria e computazionali effettivi aumentano.

Per capire meglio lo sforzo computazionale richiesto, un’ulteriore analisi viene eseguita: viene calcolato il tempo medio impiegato dall’algoritmo su 1000 iterazioni, per differenti valori di x e C. Vengono analizzati i casi x = 200 e x = 400, mentre C viene creato scegliendo i primi n numeri primi maggiori di 2. In particolare, vengono studiati i casi n = 5 e n = 10. I risultati vengono mostrati nella tabella sottostante: quando x = 200 e n = 5, l’algoritmo impiega in media t = 42 * 10^(-5) secondi; quando la lunghezza C aumenta a n = 10, il tempo medio raddoppia all’incirca, come ci si aspetta; un raddoppio di x, invece, si rispecchia in un tempo computazionale più che raddoppiato. Quando entrambi i valori di x e n vengono raddoppiati, il tempo computazionale è circa 4 volte quello iniziale. Questi risultati sono in linea con il tempo pseudo-polinomiale teorico di tipo O(nx).

Inputs		Output
x	n	time
200	5	42 * 10^(-5)
200	10	78 * 10^(-5)
400	5	97 * 10^(-5)
400	10	160 * 10^(-5)

Next Section - Ancora su programmazione dinamica: distanza tra stringhe