Proyecto Euler31: Comprensión de la solución del programa

Question

Estoy tratando de entender una solución a Proyecto Euler #31 Encontré en los foros.

El problema es que se nos dan monedas con los siguientes valores:

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

Tenemos la tarea de generar todas las formas posibles de llegar a 200. Por ejemplo, 10*10+100 = 200 sería una forma posible.

1. Pregunta 2: ¿Cómo funciona el código a continuación! Se ve muy elegante, simple y directo en comparación con mi enfoque, y corre mucho más rápido.

Mientras navegaba por los foros, encontré esta solución:

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 primera línea es solo la lista de los valores de la moneda. La segunda línea es crear una matriz con un 1 seguido de 200 0. Pero las siguientes cuatro líneas me confundieron. Creo que está incrementando la cantidad de formas posibles en la matriz, por lo que Case_num [200] dará la última entrada en la lista, pero no tengo idea de cómo funciona.

Answer 1

Esta es una solución muy buena como dijiste. El código se basa en sí mismo a través de cada iteración de 1-200 con cada denominación de monedas.

La matriz Case_num inicialmente consiste en [1, 0, 0, 0, 0, 0 ... 0, 0, 0

Lo que significan estos números (aparte de la 1) inicial son cuántas formas en que puede acumular al total dado (representado por el índice del número) usando las monedas en P_List que ha iterado hasta ahora.

La primera moneda en p_list es 1. Entonces, si 1 puede caber dentro del índice, entonces toma el valor en el índice anterior y la agrega a su índice actual. Esto funciona porque si hay 5 formas conocidas de llegar a 25 y acaba de encontrar monedas de tamaño 1, entonces también habrá 5 formas de llegar a 26. [Cada una de las 5 formas anteriores de llegar a 25] + una moneda 1 .

Entonces, después de iterar con 1, terminarás con [1, 1, 1, 1, 1 ... 1, 1

Ahora te mueves en monedas. Esta vez está utilizando una moneda de 2. Vamos a caminar por el proceso 1 más tiempo. Si 2 es menor que el índice, entonces agrega la cantidad de formas de llegar al índice anterior a su índice actual.

Por ejemplo, 2 no encaja dentro del índice 1, pero se ajusta al índice 2. Por lo tanto, simplemente creó una nueva forma de llegar a 2 a partir de 0 para tomar todas las formas en que podría llegar a 0 y agregarlos a su índice actual. En el índice 27, 2 se ajusta dentro del índice para que tome la cantidad de formas en que podría llegar a 25 y agregarlos a 27 porque ahora tiene (todas esas formas de llegar a 25 + una 2 monedas) + (todas las formas Tenías que llegar a 27 antes de saber que tenías monedas de tamaño 2).

Entonces, después de iterar con 2, terminarás con [1, 1, 2, 2, 3, 3, 4, 4 ...

Si todavía tiene problemas, puede valer la pena intentar recorrer todo el programa (tal vez en un total reducido como 50 en lugar de 200).