Project Euler31: comprensione della soluzione del programma

Question

Sto cercando di capire una soluzione a Project Euler #31 Ho trovato nei forum.

Il problema è che ci vengono fornite monete con i seguenti valori:

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

Abbiamo il compito di generare tutti i modi possibili per raggiungere 200. Ad esempio, 10*10+100 = 200 sarebbe un modo possibile.

1. Domanda 2: come funziona il codice seguente! Sembra molto elegante, semplice e diretto rispetto al mio approccio e funziona molto più velocemente.

Mentre stavo sfogliando i forum, ho trovato questa soluzione:

p_list = [1, 2, 5, 10, 20, 50, 100, 200]
case_num = [1] + [0] * 200
for i in p_list:
    for j in range(1, 201):
        if i <= j:
            case_num[j] += case_num[j-i]
print case_num[200]

La prima riga è solo l'elenco dei valori della moneta. La seconda riga sta creando un array con un 1 seguito da 200 0. Ma le prossime quattro righe mi hanno confuso. Penso che stia aumentando il numero di modi possibili nell'array, quindi Case_num [200] darà l'ultima voce nell'elenco, ma non ho idea di come funzioni.

Answer 1

Questa è una soluzione molto bella come hai detto. Il codice si basa su se stesso attraverso ogni iterazione di 1-200 con ogni denominazione della moneta.

L'array case_num inizialmente è costituito da [1, 0, 0, 0, 0, 0 ... 0, 0, 0

Ciò che questi numeri (a parte l'Internity 1) significano sono quanti modi puoi costruire fino al totale dato (rappresentato dall'indice del numero) usando le monete in p_list che hai iterate finora.

La prima moneta in P_LIST è 1. Quindi se 1 può inserirsi all'interno dell'indice, si prende il valore nell'indice precedente e aggiungilo all'indice corrente. Funziona perché se ci sono 5 modi noti per arrivare a 25 e hai appena trovato monete della dimensione 1, ci saranno anche 5 modi per arrivare a 26. [Ognuno dei 5 modi precedenti per arrivare a 25] + uno 1 moneta .

Quindi, dopo aver ripetuto con 1, finirai con [1, 1, 1, 1, 1 ... 1, 1

Ora ti muovi nelle monete. Questa volta stai usando una moneta di 2. Segnaliamo attraverso il processo 1 in più. Se 2 è inferiore all'indice, si aggiunge il numero di modi per arrivare all'indice precedente all'indice corrente.

Ad esempio 2 non rientra nell'indice 1 ma si adatta all'indice 2. Quindi hai appena creato un nuovo modo per arrivare a 2 da 0 in modo da prendere tutto il modo in cui potresti arrivare a 0 e aggiungerli al tuo indice corrente. Sull'indice 27, 2 si adattano all'indice in modo da prendere il numero di modi in cui potresti ottenere a 25 e aggiungerli a 27 perché ora hai (tutti quei modi per arrivare a 25 + uno 2 monete) + (tutti i modi Dovevi arrivare a 27 prima di sapere di avere monete di taglia 2).

Quindi, dopo aver ripetuto con 2, finirai con [1, 1, 2, 2, 3, 3, 4, 4 ...

Se hai ancora problemi, potrebbe valere la pena provare a percorrere l'intero programma (forse a un totale ridotto come 50 anziché 200).