Home > Project Euler, python > Problem Euler #31

Problem Euler #31

In England the currency is made up of pound, £, and pence, p,
and there are eight coins in general circulation:

    1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

    1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Su questo problema ho trovato svariate soluzioni in internet, dalla
BruteForce, che anche io ho adottato inizialmente, ai forloop compattissimi
che ti danno il risultato esatto senza un briciolo di spiegazione.

Poi ho trovato questo sito:
dove, FINALMENTE, si spiega ciò che si codifica.

Si accenna alla programmazione dinamica (qui wikipedia aprirà un mondo a parte).

Il sito è in inglese e cercherò brevemente di tradurre l’analisi del problema.

Creiamo una tabella dove avremo i seguenti campi:

+--------+---------+------+------+-------+-------+-------+--------+--------+
| target | only 1p | <=2p | <=5p | <=10p | <=20p | <=50p | <=100p | <=200p |
+--------+---------+------+------+-------+-------+-------+--------+--------+

target è il totale che vogliamo raggiungere in cents e le successive colonne
indicano le monete da utilizzare.

– cominciamo con il primo target: 1cents
quante possibilità ci sono di formare 1cents, con monete da 1pence?
Solo una: 1x1p (una moneta da 1 pence)
Con tutte le aaltre monete a disposizione?
Sempre e solo una possibilità, ad es.: avendo monete di taglio <= 2p, l'unica
possibilità sarà sempre e solo 1x1p.
Possiamo quindi riempire tutta la prima fila:

+--------+---------+------+------+-------+-------+-------+--------+--------+
| target | only 1p | <=2p | <=5p | <=10p | <=20p | <=50p | <=100p | <=200p |
+--------+---------+------+------+-------+-------+-------+--------+--------+
|    1   |     1   |   1  |   1  |   1   |   1   |   1   |    1   |    1   |
+--------+---------+------+------+-------+-------+-------+--------+--------+

– passiamo al secondo target: 2cents
Quante possibilità ci sono di formare un totale di 2cents con monete di 1pence?
Solo una: 2x1p ( 2 monete da 1 pence)
Quante possibilità con monete <= 2p?
Sono due: 2x1p ( 2 monete da 1 pence) e 1x2p (una moneta da 2 pence)
Ovviamente aggiungere monete di taglio superiore non cambia nulla, le combinazioni
rimarranno 2.
Compiliamo quindi la seconda riga della tabella:

+--------+---------+------+------+-------+-------+-------+--------+--------+
| target | only 1p | <=2p | <=5p | <=10p | <=20p | <=50p | <=100p | <=200p |
+--------+---------+------+------+-------+-------+-------+--------+--------+
|    1   |     1   |   1  |   1  |   1   |   1   |   1   |    1   |    1   |
+--------+---------+------+------+-------+-------+-------+--------+--------+
|    2   |     1   |   2  |   2  |   2   |   2   |   2   |    2   |    2   |
+--------+---------+------+------+-------+-------+-------+--------+--------+

Attenzione, i numeri posti nelle celle indicano il numero di combinazioni,
NON di monete utilizzate!!!

– passiamo al terzo target: 3cents
3 cents si formano così: 3x1p, 1x1p + 1x2p – 2 combinazioni
4 cents si formano così: 4x1p, 2x1p + 1x2p, 2x2p – 3 combinazioni
5 cents si formano così: 5x1p, 3x1p + 1x2p, 1x1p + 2x2p + 1x5p – 4 combinazioni

e così via…

Che cosa si nota da questa tabella?

+--------+-----+------+------+-------+-------+-------+--------+--------+
| target |  1p | <=2p | <=5p | <=10p | <=20p | <=50p | <=100p | <=200p |
+--------+-----+------+------+-------+-------+-------+--------+--------+
|    1   |  1  |   1  |   1  |   1   |   1   |   1   |    1   |    1   |
+--------+-----+------+------+-------+-------+-------+--------+--------+
|    2   |  1  |   2  |   2  |   2   |   2   |   2   |    2   |    2   |
+--------+-----+------+------+-------+-------+-------+--------+--------+
|    3   |  1  |   2  |   2  |   2   |   2   |   2   |    2   |    2   |
+--------+-----+------+------+-------+-------+-------+--------+--------+
|    4   |  1  |   3  |   3  |   3   |   3   |   3   |    3   |    3   |
+--------+-----+------+------+-------+-------+-------+--------+--------+
|    5   |  1  |   3  |   4  |   4   |   4   |   4   |    4   |    4   |
+--------+-----+------+------+-------+-------+-------+--------+--------+

1 – La prima colonna è sempre riempita con valore 1
2 – Quando compiliamo una cella, guardiamo che valore di monete abbiamo a
disposizione.
2A – Se il valore del target è minore della moneta massima disponibile
(colonna), copiamo il valore della colonna precedente. Questo è logico, per un
target di 4 cents con monete <= 2p abbiamo 3 combinazioni, aggiungendo la moneta
da 5p non cambia nulla perchè sforiamo dal target, quindi il numero di combinazioni
non varia.
2B – Se il valore del target è maggiore o uguale alla "colonna", il numero delle
combinazioni sarà dato dalla somma del numero di combinazioni della colonna precedente,
e il valore delle combinazioni della differenza tra target e "colonna", sempre nella
stessa colonna:
Subito un esempio:
Prendiamo il target 5:
Per la colonna <= 2p, avremo un numero di combinazioni data dalla somma delle
combinazioni precedenti (1p), quindi 1
più il numero delle combinazioni della differenza tra il target e il "max-coin"
di colonna (<=2p):
target – maxcoin = 5-2 = 3
Le combinazioni per il "nuovo" target 3 alla colonna "<= 2p", sono 2.
Quindi la somma sarà 1+2 = 3.
Nella cella (5,2p) avremo un 3. Questo è compilabile da qui all'infinito.
Codificando con questo "trucchetto" il tutto, abbatteremo in maniera pazzesca
i tempi di esecuzione.
In onore dell'autore, che ha utilizzato un dizionario come "matrice", ho voluto
almeno utilizzare una lista per fare la stessa cosa:

import time

ts = time.time()

coins = [1, 2, 5, 10, 20, 50, 100, 200]
total = 200
matrix = []

for comb in range(0, total + 1):
    matrix.append([1]*len(coins)) # create grid 200x8

# first and second rows to 1
# first column to 1
# so...

for target in xrange(2, total +1): # first 2 rows excluded 
    for p in xrange(1, len(coins)): # first column excluded
        if target >= coins[p]:
            matrix[target][p] = matrix[target][p-1] + matrix[target-coins[p]][p]
        else:
            matrix[target][p] = matrix[target][p-1]


#for row in matrix: print row
print matrix[200][len(coins)-1]
print time.time() - ts

Metodo 2:

Una semplificazione del problema è quella di usare al posto di una matrice
una lista semplice. In pratica la lista sarà formata dai 200 target che dovremo
trovare (0-200).
Inizializziamo il target 0 ad 1 e poi scopriamo man mano i target successivi.
Per comodità riassumeremo con soli 5 target:

+------+-----------------------+
|      |       target          | 
+------+---+---+---+---+---+---+
| coin | 0 | 1 | 2 | 3 | 4 | 5 |
+------+---+---+---+---+---+---+
|  1p  | 1 | 0 | 0 | 0 | 0 | 0 |
+------+---+---+---+---+---+---+

Lo zero viene inizializzato a 1.
Il pattern è sempre il medesimo:
A) se il target è minore del coin utilizzato, si prende come valore di
combinazioni quello precedente (della stessa colonna),

B) se il target è maggiore u uguale al coin utilizzato, si utilizza la formula
target – coin + (valore delle combinazioni precedenti nella stessa colonna)

Non c’è bisogno di un pattern per capire che con solo una moneta da 1p
per comporre i vari target, c’è sempre e solo una combinazione:

1p * target = 5 x 1p

comunque sia ad eccezion fatta per 0 (inizializzato ad 1) abbiamo che target 1
è uguale a 1 (B) quindi target – coin = 1 – 1 = 0
prendiamo il valore presente nella colonna 0 (1) e lo sommiamo allo 0 presente
in colonna 1.
con target 2 (B):
2 – 1(p) = 1 -> 1 + 0 = 1 e così via

quindi avremo:

+------+-----------------------+
|      |       target          | 
+------+---+---+---+---+---+---+
| coin | 0 | 1 | 2 | 3 | 4 | 5 |
+------+---+---+---+---+---+---+
|  1p  | 1 | 1 | 1 | 1 | 1 | 1 |
+------+---+---+---+---+---+---+

Vediamo la moneta da 2p:
ricordiamo che la colonna del target 0 è per definizione tutta a 1, quindi
passiamo al target 1

+------+-----------------------+
|      |       target          | 
+------+---+---+---+---+---+---+
| coin | 0 | 1 | 2 | 3 | 4 | 5 |
+------+---+---+---+---+---+---+
|  2p  | 1 | 1 | 1 | 1 | 1 | 1 |
+------+---+---+---+---+---+---+
             ^

il target (1) è minore di 2p (A) quindi la combinazione rimane la precedente.
In effetti 1 è ottenibile solo con 1x1p 2p non ci serve.
target 2 (B): utilizziamo il pattern
target – coin = 2 – 2 = 0
le combinazioni su 0 sono 1, più il valore esistente dal precedente ciclo
con 1p (1) ci dà come valore 2.

+------+-----------------------+
|      |       target          | 
+------+---+---+---+---+---+---+
| coin | 0 | 1 | 2 | 3 | 4 | 5 |
+------+---+---+---+---+---+---+
|  2p  | 1 | 1 | 2 | 1 | 1 | 1 |
+------+---+---+---+---+---+---+
                 ^

con il 3p:
3 – 2 = 1 -> 1 (colonna 1) + 1 (esistente) = 2

+------+-----------------------+
|      |       target          | 
+------+---+---+---+---+---+---+
| coin | 0 | 1 | 2 | 3 | 4 | 5 |
+------+---+---+---+---+---+---+
|  2p  | 1 | 1 | 2 | 2 | 1 | 1 |
+------+---+---+---+---+---+---+
                     ^

completando i restanti target:
4 – 2 = 2 -> 2 (colonna 2) + 1 (esistente) = 3
5 – 2 = 3 -> 2 (colonna 3) + 1 (esistente) = 3

risulta:

+------+-----------------------+
|      |       target          | 
+------+---+---+---+---+---+---+
| coin | 0 | 1 | 2 | 3 | 4 | 5 |
+------+---+---+---+---+---+---+
|  2p  | 1 | 1 | 2 | 2 | 3 | 3 |
+------+---+---+---+---+---+---+

Il target 5 ci dà come numero di combinazioni 3; in effetti 5 è ottenibile
con 2x2p + 1x1p, 1x2p + 3x1p e 5x1p.

Si procede con lo stesso metodo fino al termine delle monete disponibili.

Il codice che ne consegue è:

import time

START = time.time()

def eu_31(limit):
    qty = [0] * (limit + 1)
    qty[0] = 1
    for coin in (1,2,5,10,20,50,100,200):
        for i in range(coin, limit + 1):
            qty[i] += qty[i-coin]
    return qty[limit]

print "euler 31: {}".format(eu_31(200))
print time.time() - START

altri link utili:
Project Euler
Programmazione dinamica

Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  1. No trackbacks yet.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: