Tip:
Highlight text to annotate it
X
El siguiente contenido se suministra bajo un Licencia de Creative Commons. Su apoyo
ayudar a MIT OpenCourseWare continuar ofreciendo recursos de alta calidad de la educación de forma gratuita.
Para hacer una donación o ver material adicional en cientos de cursos del MIT, visite el MIT OpenCourseWare
en ocw.mit.edu. PROFESOR: OK. Quiero empezar donde lo dejamos
fuera. ĘRecuerdas la última vez que estábamos buscando en Fibonacci. Y así lo tenemos aquí,
una buena aplicación poco recursiva de que. Y lo que yo quería seĄalar es,
tenemos este número variable global de las llamadas. Lo que no existe porque las necesidades de Fibonacci
ella, pero sólo por razones pedagógicas, de modo que podemos hacer un seguimiento de la cantidad de trabajo esta cosa
está haciendo. Y me he convertido en una instrucción de impresión que fue la última vez. Así podemos ver lo que
que está haciendo es que se ejecuta. Así que vamos a tratar aquí con Fib de 6.
Así que, como esperamos, Fib de 6 pasa a el 8. Ese derecho? Este derecho, todo el mundo? En caso de
Fib, de 6 de 8? No creo así. Así que primero Lo que debemos hacer es rascamos la cabeza y
ver lo que está pasando aquí.
Bien, echemos un vistazo a él. ĘQué está pasando en esta lista? Esta es su llamada de despertador por la maĄana. ĘQué está pasando? Sí.
[Inaudible]: ESTUDIANTE PROFESOR: A ver si lo puedo conseguir todo el camino
en la parte posterior. No, no puedo. Eso es vergonzoso. Muy bien. Así que si n es menor o igual a
1, vuelva n. Bueno, eso no está bien, Ęverdad? ĘQué debo estar haciendo allí? Debido a Fib
de se? ĘQué? 1. Así que vamos a arreglarlo. ĘQué tal , Ęverdad? O tal vez, lo que sería aún
más simple que eso? Tal vez debería hacer que.
Ahora vamos a probarlo.
Nos sentimos mejor acerca de esto? Nos gusta esta respuesta? Sí, Ęno? ĘCuál es la respuesta, chicos? ĘQué debe de Fibonacci
de 6 de se? Creo que esa es la respuesta correcta, Ęno? Aceptar.
Entonces, Ęqué es lo que quiero que te des cuenta de esto? He calculado un valor que es 13. Y es
me llevó 25 llamadas. 25 llamadas recursivas para obtener allí. ĘPor qué está teniendo tanta gente? Bueno, lo que
podemos ver aquí es que yo soy el cálculo del mismo valor una y otra vez. Porque si
nos fijamos en la estructura recursiva de la programa, lo que vamos a ver que está pasando aquí
es decir, que yo llamo Fib de 5 y 4, pero luego de Fib 5 también se va a llamar Fib de 4. Así que me voy
que es la informática en las ramas. Y a continuación, se pone peor y peor, ya voy hacia abajo.
Así que si pienso en la informática de Fib voy a la informática que un montón de veces. Ahora,
afortunadamente, Fib de 0 es corto. Pero el otro los que no son tan cortos. Y así lo que veo es
que mientras corro, estoy haciendo un montón de despedidos computación. Calcular los valores cuya respuesta
Ya debe saber. Eso es, usted recordará la última vez, hablé acerca de la noción de acumulación
sub-problemas. Y eso es lo que tenemos aquí. Como ocurre con muchos algoritmos recursivos, resuelvo
un problema mayor por la solución de una instancia más pequeĄos del problema original. Pero aquí no hay
se superponen. La instantánea a diferencia de búsqueda binaria, en cada caso era distinto, aquí el
casos se superponen. Ellos comparten algo en comunes. De hecho, comparten mucho en
comunes. Eso no es inusual. Eso me llevó a utilizar una técnica que he mencionado
otra vez la última vez, memoization llamada. En efecto, lo que dice es, se registra un valor de la primera
vez que se calcula,
a continuación, mirar hacia arriba
los tiempos posteriores lo necesitamos. Así que tiene sentido. Si sé que voy a
Necesito algo más de una y otra vez, me ardilla que en algún lugar y luego recuperarlo cuando
Lo necesito. Así que vamos a ver un ejemplo de que.
Así que voy a tener algo que se llama rápida Fib. Pero primero voy a tener, vamos a ver
en lo rápido Fib hace y entonces va a venir Volviendo a la pregunta siguiente. Se toma el número de
cuya Fibonacci quiero más una nota.
Y la nota será un diccionario que se asigna me de un número de Fibonacci de ese número.
Así que lo que voy a hacer, bueno, vamos a deshacernos de esta sentencia print por ahora. Voy
decir, si n no es de nota. Recuerde que la forma diccionario funciona, esta es la clave. Es
la clave de un valor. Entonces voy a llamar rápido Fib recursivamente, con n menos 1 de cada nota, y n
menos dos en el memorándum. De lo contrario voy a devolver el nota.
Bueno, vamos a ver por un segundo. Este es la idea básica. Pero, Ęrealmente creen
esto va a funcionar? Y, de nuevo, quiero a ver esto y pensar en lo que
va a pasar aquí. Antes de hacer eso, o como se hace eso, vamos a ver Fib 1. La clave
cosa a notar sobre Fib 1 es que ha la misma especificación que Fib. Porque cuando
alguien llama a Fibonacci, que no debe preocuparse acerca de las notas. ĘY cómo lo había aplicado. Que
tiene que ser bajo las sábanas. Así que no quiero que tiene que llamar a algo con dos argumentos.
El entero y la nota. Así que voy a crear Fib 1, que tiene los mismos argumentos que Fib. La
Lo primero que hace es que inicializa la nota. Y inicializa diciendo, si me
I - gritos. Ajá. Vamos a tener cuidado aquí. Si Me vuelvo un 0. Me uno, vuelvo 1. Así que
Puse dos cosas en la nota ya. Y entonces voy a llamar rápido Fib y lo devuelve al
resultado que tiene. Así que ya ves la idea básica. Tomo algo
con los mismos parámetros que el original. Agregar esta nota. Dale un poco de los valores iniciales.
Y a continuación, llamar. ĘY ahora qué pensamos? Es esto va a funcionar? ĘO hay un problema aquí?
ĘQué piensa usted? Piensa en ella. Si se trata de no en la nota, voy a calcular su valor y
lo puso en la nota. Y entonces voy a devolverlo. ĘDe acuerdo? Si ya estaba allí, sólo que se vea
arriba. Que tengan sentido para todo el mundo? Vamos a ver qué pasa si lo ejecutan. Bueno,
de hecho, vamos a su vez la declaración de imprimir, ya que estamos haciendo con un valor pequeĄo aquí.
Así que lo que hemos visto es que he ejecutarlo dos veces aquí. Cuando se corrió aquí, con el viejo Fib, y
imprimimos el resultado, y lo corrió con Fib Uno aquí. La buena noticia es que tenemos 13 tanto
veces. La mejor noticia es que en lugar de 25
pide, no fue hasta 11 llamadas.
Así que es una gran mejora. Vamos a ver lo que sucede, sólo para tener una idea de cuán grande es el
mejora. Voy a sacar el dos declaraciones de impresión. Y vamos a intentarlo con un número más grande.
Va a tomar un poco. Bueno, mira en esta diferencia. Es frente a 2.692.537
59. Esa es una gran diferencia bastante maldito. Y No voy a pedirle que compruebe si tiene la
respuesta correcta. Al menos, no en la cabeza. Así que usted puede ver, y esto es una cosa importante
vemos, es que si nos fijamos en el crecimiento, no parecía que le importaba mucho con
6. Debido a que era un pequeĄo número a una número ligeramente menor. Pero esta cosa crece
de manera exponencial. Es un poco complicado exactamente cómo. Pero se puede ver como voy a
30 Puedo obtener un número bastante grande. Y 59 es un muy pequeĄo número. Así vemos que el memoization
aquí me está comprando una gran ventaja. Y esto es lo que está en el corazón de este
muy técnica general convocada programación dinámica. Y de hecho, se encuentra en el corazón de un lote
útiles de técnicas computacionales en el que guardar los resultados. Así que si usted piensa acerca de la forma
algo así como, por ejemplo, Mapquest obras, y el último semana en la recitación que miró por el hecho de
que el camino más corto es exponencial. Bueno, lo que lo que hace es que ahorra una gran cantidad de caminos. En cierto modo
sabe de la gente va a preguntar cómo lo hace ir de Boston a Nueva York. Y puede
que ha guardado. Y si usted va de Boston a otro lugar de Nueva York, donde sólo
pasa a estar en el camino, que no tiene para volver a calcular que parte de ella. Así que es guardado
un montón de cosas y ellos se guardaron. Y eso es básicamente lo que estamos haciendo aquí.
Aquí lo estamos haciendo como parte de un algoritmo. No, son sólo el almacenamiento de una base de datos
previamente resuelto los problemas. Y confiando en algo que se llama tabla de consulta, de los cuales memoization
es un caso especial. Pero tabla de búsqueda es muy comunes. Cuando usted hace algo complicado
guardar las respuestas y luego ir a buscarlo más tarde.
Debo aĄadir que, en cierto sentido se trata de un falso hombre de paja de Fibonacci. Nadie en su
sano juicio aplica efectivamente una recursiva Fibonacci de la manera que lo hizo originalmente. Debido a que
de la manera correcta de hacerlo es iterativo. Y la forma correcta de hacerlo no es a partir de las
la parte superior, que está empezando en la parte inferior. Y lo que se puede reconstruir de esa manera. Sin embargo,
no te preocupes por eso, no lo es, estoy usando porque es un ejemplo más sencillo que el
uno que realmente quiero llegar, que es la mochila. Bueno, la gente se esta? Y ver la idea básica
y por qué es maravilloso? Muy bien. Ahora, cuando hablamos de problemas de optimización
en la programación dinámica, me dijo que había dos cosas para buscar. Uno de ellos fue la superposición
sub-problemas. Y el otro era óptima subestructura. La idea aquí es que usted
puede obtener una solución óptima desde el mundo local soluciones óptimas a los sub-problemas.
Esto no es cierto de todos los problemas. Sin embargo, como veremos ver, es el caso de un montón de problemas. Y cuando
usted tiene una subestructura óptima y lo local Las soluciones se solapan, es cuando usted puede traer
programación dinámica de soportar. Así que cuando usted está tratando de pensar es este un problema que
Yo puedo resolver con programación dinámica, estos son las dos preguntas que usted hace.
Ahora vamos a volver atrás y crear instancias de estas ideas para el problema de la mochila que vimos por última vez
tiempo. En particular, para la mochila 0-1 problema. Por lo tanto, tenemos una colección de objetos.
Lo llamaremos a. Y para cada objeto en 0, tenemos un valor. En una, tenemos un valor. Y
Ahora queremos encontrar el subconjunto de que se ha el valor máximo, sujeto a la restricción de peso.
Sólo estoy repitiendo el problema. Ahora, lo que vimos la última vez es que hay un bruto
vigor solución. Como usted ha descubierto en conjunto de problemas recientes, es posible construir
todos los subconjuntos de un conjunto. Y por lo que podría construir todos los subconjuntos, compruebe que el peso es menor
que el peso de la mochila, y luego elegir el subconjunto con el valor máximo.
O un subconjunto con el valor máximo, no Puede haber más de uno, y ya está.
Por otro lado, hemos visto que si el tamaĄo de una es n, es decir, tenemos n elementos
para elegir, entonces el número de posibles subconjuntos es 2 a la n. Recuerde, vimos que
la última vez mirando a los números binarios. 2 a la n es un número grande. Y tal vez no
tiene que considerar todo, porque podemos digo, oh éste va a ser demasiado grande.
Esto va a aumentar mucho de peso, no necesitamos para mirarlo. Pero todavía será para dos
a la n. Si n es algo así como 50 no, un número grande, 2 a la 50 es un número enorme.
Así que vamos a preguntar, Ęexiste una subestructura óptima a este problema. Eso nos permitiría hacer frente a
con programación dinámica. Y vamos para ello inicialmente por mirar un sencillo
aplicación basada en lo que se llama el árbol de decisión.
Este es un concepto muy importante, y nos va a ver una gran cantidad de algoritmos esencialmente aplicar
árboles de decisión. Veamos un ejemplo. Supongamos que los pesos, y lo intentaré
un ejemplo muy pequeĄo para empezar, son 5, 3 y 2, y los valores, correspondientes
valores, de 9, 7 y 8. Y el máximo, vamos a por ejemplo, es de 5.
Así que lo que hacemos es empezar por considerar por cada artículo si tomarlo o no. Por
razones por las que llegarán a ser evidentes cuando implementarlo en el código, voy a empezar a
la parte de atrás. El último elemento de la lista. Y lo que voy a utilizar es el índice de ese
elemento para realizar un seguimiento de dónde estoy. Así que estoy No voy a preocupar si este elemento es un
florero o un reloj o la pintura. Voy decir que es el elemento n-ésima. Donde n-ésima es
en algún lugar entre el 2 y en este caso. Y entonces vamos a construir nuestro árbol de la siguiente manera:
cada nodo, así, permítanme poner un ejemplo aquí. El primer nodo se la tire a 2, 5 y
0.
Permanente a favor, déjame asegurarme de obtener este en el orden correcto, así, el índice que
es 2, el último elemento en este caso, por lo que es el índice. Este es el peso todavía está disponible.
Si usted ve que en la sombra. Y esto es el valor obtenido actualmente. Así que no tienen
incluye cualquier cosa. Significa que tengo todas las cinco libras izquierda. Pero no tengo nada de valor.
Ahora, el árbol de decisión, si la rama izquierda, es un árbol binario. Esto va a ser no
tomar. Así que no voy a tomar el tema con un índice de 2. Lo que significa este nodo
tienen un índice de 1. Siguiente tema a considerar, todavía tengo 5
libras disponibles. Y tengo valor. Para ser sistemática, yo voy a construir este árbol en profundidad
dejó de sesiones.
En cada nodo, me voy a ir a la izquierda hasta que no puede ir más lejos. Así que vamos a tomar otro
; no toma sucursal aquí. ĘY cuál es este nodo va a parecer? ĘPerdón?
[Inaudible]: ESTUDIANTE PROFESOR: 0, 5, 0. Y luego nos vamos un
más. Y yo sólo voy a poner un signo menos que indica Ya he terminado. No puedo mirar debajo. Todavía
tienen cinco libras a la izquierda, y todavía tengo cero valor.
Lo siguiente que voy a hacer es dar marcha atrás.
Es decir, me voy a volver a un nodo que ya he visitado. Sube por el árbol
1. Y ahora, por supuesto, el único lugar para ir tiene razón. Y ahora tengo que incluir algo.
Sí. ĘY qué significa esta mirada como nodo? Bueno, Te daré una pista, que comienza con un signo menos.
ĘY ahora qué? [Inaudible]: ESTUDIANTE
PROFESOR: Perdón. 0. ĘY? [Inaudible]: ESTUDIANTE
PROFESOR: ĘPerdón? 5. Muy bien. Hasta ahora, este Parece que el ganador. Pero, lo mejor será mantener
va. Tenemos que dar marcha atrás una vez más. No hay nada útil que hacer. Estamos aquí para dar marcha atrás.
Y nos preguntamos, Ęqué queremos conseguir con este nodo? 0, 3. Alguien?
[Inaudible]: ESTUDIANTE PROFESOR: Más fuerte. 2. ĘY después?
[Inaudible]: ESTUDIANTE PROFESOR: No hay un valor aquí, Ęqué es esto
valor? He incluido un número de artículo 1, que tiene un valor de 7. ĘNo? Así que ahora esto se ve como el ganador. ĘPerdón?
[Inaudible]: ESTUDIANTE PROFESOR: Este?
ESTUDIANTE: Sí. [Inaudible] PROFESOR: Recuerda, yo estoy trabajando desde el
espalda. Por lo tanto, no debe ser 9. En caso de ser qué? Punto 0, oh, estás en lo cierto, es de 9 puntos. Gracias
usted. Tienes razón. Sin embargo parece que el ganador. No puedo oír.
[Inaudible]: ESTUDIANTE PROFESOR: Vamos a tener cuidado con esto. Estoy
la gente feliz está viendo. Así que estamos aquí. Y ahora tenemos cinco libras disponibles. Eso es bueno.
Y estamos teniendo en cuenta el número de artículo 0. ĘQué sucede a pesar 5 libras. Así que esa es una buena
cosa. Por lo tanto, es el último elemento a considerar. Si lo son, vamos a tener nada.
Debido a que tenían 5 y estamos utilizando todos los 5. Así que que será 0. Y su valor es de 9. Por lo tanto,
poner un elemento en la mochila y nos hemos un valor de 9. ĘAlguien tiene un problema con eso?
Hasta ahora, todo bien? Ahora que hemos apoyado hasta aquí. Estamos considerando
el punto 1 y que estamos tratando de preguntarnos si estamos puede poner pulg artículo 1 tiene un peso de 3. Así que
sería conveniente. Y si la usamos, tenemos 2 libra la izquierda. Y el artículo 1 tiene un valor de 7.
Así que si lo hiciéramos esto, tendríamos un valor de 7. Pero no hemos terminado aún, Ęno? Todavía tenemos
algunas cosas a considerar. Bueno, podríamos considerar no poner en el punto 0. Eso hace al maestro
sentido. Y estamos de vuelta a donde hemos llegado, menos 2 y 7.
Y ahora vamos a pedir a la pregunta de cómo, alrededor de poniendo en el punto 0. Bueno, no podemos. Debido a que
lo que pesó 5 libras, sólo tengo 2 a la izquierda. Así que no hay rama derecha de éste. Así que estoy haciendo lo que las decisiones que puedo hacer
en el camino. Vamos a volver hasta aquí. Y Ahora vamos a preguntar acerca de tomar el punto 2.
Si tomamos el punto 2, a continuación, así, el índice después de que, por supuesto, 1. Y la disposición
el peso será de 3. Y el valor será de 8, Ęno? Muy bien, ahora decimos, Ępuedo tomar el tema
1. Sí. Que pueda. Sólo pesa 3 y sucederá que tener 3 a la izquierda. Así que eso es bueno. No tome
que, a la derecha. Lo sentimos. Este es el no tener poder. Así que voy a 0, 3, 8. Y entonces puedo hacer otra
no tienen sucursales. Y esto me lleva a lo que, menos 3, 8. Ahora voy a una copia de seguridad. Y yo le digo:
bien, supongo que tienen el punto 0, así que no puede tomar el punto 0, Ęno? Pesa demasiado.
Por lo tanto, no tienen esa rama. Volver hasta aquí. Bien, puedo tomar el punto 1? Sí, puedo. Y
eso me da qué? [Inaudible]: ESTUDIANTE
PROFESOR: Tenemos un ganador. Así que es de tedioso, pero es importante ver que
funciona. Es sistemático. Tengo una forma de explorar las posibles soluciones. Y en el
final que elija el ganador.
ĘCuál es la complejidad de este árbol de decisión solución? Bueno, en el peor de los casos, estamos enumerando
todas las posibilidades de entrada y salida. Ahora que he acortar un poco diciendo, ah, hemos
se queda sin peso, estamos bien. Pero efectivamente es, como vimos antes, exponencial. 2 a
n, todos los valores en el vector poco vimos en la última vez es 0 o 1. Así que es un binario
número de n bits, 2 a la n. Echemos un vistazo a una implementación directa
de este. Me libraré de Fibonacci aquí, no quieres que te molestes en buscar en eso otra vez.
Espera un segundo hasta que comento esto, sí.
[Inaudible]: ESTUDIANTE PROFESOR: Sí. Hay una rama que podríamos
terminar aquí, pero ya que estamos fuera de peso que tipo de saber que vamos a hacer. Así que
que pudiera terminar. Pero no es muy interesante. Pero sí, probablemente debería haber hecho eso.
Así que vamos a ver una puesta en práctica aquí. Gritos. ĘHa tenido esto en el folleto, por cierto.
Así que aquí está máx val. Se toma cuatro argumentos. El peso, w, y V, estos son los dos vectores
que hemos visto aquí. De los pesos y los valores. Toma i, que es en cierto sentido, la longitud
de esos, menos 1 vectores, debido a la manera Python funciona. Así que me da mi índice.
Y la cantidad de peso disponible, w, por peso disponible.
Así que de nuevo, me puse, a este número, que puede ignorar. La primera línea dice, si i es 0, que
significa que estoy buscando en el elemento último. Entonces, si el peso de i es menor que la disponible
peso, que puede devolver el valor de i. De lo contrario es 0. Tengo uno de los elementos a la vista. I
o bien poner en si puedo. Si no puedo, no lo hago. Muy bien, por lo que si estoy en el final de la cadena,
ese es mi valor. En cualquier caso, si yo estoy buscando en el último elemento, que yo regrese.
La siguiente línea dice bien, supongo que no, Yo no estoy en el último elemento. Supongamos que no
incluirlo. Entonces el valor máximo que puede conseguir es el valor máximo de lo que había. Sin embargo, con
índice i menos 1. Así que esa es la don't toma rama. Como hemos visto sistemáticamente en el
-; no tiene, lo único que se cambia es el índice.
La siguiente línea dice que si el peso de i es mayor que una w, pues bien sé que no puede poner
pulg Así que bien podría devolver el sin valor i me computarizada. De lo contrario, vamos a
ver lo que me pasa con i. Y por lo que el valor de con i será el valor de i más lo que
Que puedo conseguir con los puntos restantes y decreciente el peso por el peso de i. Así que eso es exactamente
lo que vemos a medida que bajan las ramas derecha. Miro al resto de la lista, pero he cambiado
el valor. Y he cambiado la disposición de peso.
Y luego, cuando llego al final, me voy para devolver el mayor de i con y sin
i. He calculado el valor si incluyen i. Yo calcula el valor si no incluyo i.
Y luego me voy a devolver sólo el más grande de los dos. Un poco complicado, pero es
básicamente la aplicación de esta decisión árbol.
Vamos a ver qué pasa si lo ejecutan. Bueno, lo que siempre hago en algo como esto es,
lo primero que hago es correr en algo donde realmente se puede calcular la respuesta en
mi cabeza. Así que tener una idea de si o no Estoy haciendo lo correcto. Así que aquí está un poco
ejemplo. Y yo voy a hacer una pausa por un minuto, antes de
Lo ejecuto, y pedir a cada uno para calcular en la cabeza lo que creo que la respuesta debe
se. De acuerdo con lo que dije acerca de la depuración. Supongo que siempre antes de ejecutar el programa lo
Crees que va a hacer. Y yo voy que esperar hasta que alguien levanta la mano y
me da una respuesta. Sí. ESTUDIANTE: 29?
PROFESOR: Así que tenemos una hipótesis de que la respuesta debe ser 29. Ooh. Eso es malo. Así como
personas en la parte de atrás están respondiendo a estas preguntas porque quieren poner a prueba mi brazo. La cámara probablemente no entendió, pero
fue un tiro perfecto. Cualquier otra persona que es 29? Cualquier persona que no es 29? ĘQué
crees que es? Perdón ESTUDIANTE: 62?
PROFESOR: 62. Eso sería impresionante. 62. Bien, bien, tenemos una estimación de 62 aĄos. Bueno,
vamos a correr y ver.
29 que es. Y lo hizo con un total de 13 llamadas. No lo hizo esta optimización poco que hice
por aquí. Pero nos da la respuesta. Así que eso es bastante bueno. Vamos a intentar un poco más grande
ejemplo. Así que aquí voy a utilizar el ejemplo que tuvimos
en la última vez que la clase. Este fue el ejemplo de ladrón donde había dos copias de todo. En este caso,
se obtiene un valor máximo de 48 y 85 llamadas. Así vemos que he duplicado el tamaĄo de la
vector pero yo tengo mucho más que duplicado el número de llamadas. Esta es una de estas propiedades
de este tipo de crecimiento exponencial. Bueno, vamos a ser muy valiente aquí. Y vamos a
tratar un vector muy grande. Así que esta particular vector, es probable que ni siquiera puede ver toda la cosa
en la pantalla. Bueno, tiene 40 artículos en que. Vamos a ver lo que pasa aquí. Muy bien, que me quiere decir cuál es la respuesta
mientras que se calcula la distancia? Nadie en su sano juicio. Les puedo decir la respuesta, pero
eso es porque he engaĄado, ejecute el programa antes.
Bien, esto va a tardar un poco. Y Ępor qué se va a tomar un tiempo? En realidad
no es 40, creo que estos son, está bien. Así que la respuesta es 75 y es el número de llamadas
1,7 millones. ĘPerdón? 17 millones. Computadoras son rápidos, por suerte. Bueno, eso es mucho
de las llamadas. Vamos a tratar de averiguar lo que está pasando.
Pero no vamos a tratar de averiguar lo que está pasando con este ejemplo muy, muy grande, porque vamos a
conseguir realmente cansado. Oh. En realidad, antes de hacer eso, sólo por diversión, lo que quiero hacer es
escribir para futura referencia, cuando miramos a una velocidad de uno, que la respuesta es de 75 y Eric,
cuántas llamadas? 240.000. Muy bien. Vamos a llegar de nuevo a esos números.
Veamos con un ejemplo más pequeĄos. Vamos a visita nuestro ejemplo, de 8. Que nos interesamos en
antes. Y vamos a activar esta sentencia print. Oh, Ęqué fue eso? Tenga en cuenta que sólo tengo la impresión
i y un w. ĘPor qué es eso? Debido a W y V son constante. Yo no te quiero para imprimir a través de
y otra vez.
No, mejor que lo llame. Eso sería una buena que se puede hacer, Ęverdad? Así que vamos a ver. Llamaremos
con éste. Por lo que es la impresión de un lote. Se va a imprimir, creo,
85 llamadas. Y la cosa que usted debe notar aquí es que se está haciendo una gran cantidad de la misma
las cosas una y otra vez. Así, por ejemplo, vamos a ver dos, uno aquí. Y dos, una aquí. Y 2,
1 aquí. Así como Fibonacci, que está haciendo la mismo trabajo una y otra vez. ĘCuál es el
solución? Bueno, no se sorprendió al escuchar que es
la misma solución. Así que echemos un vistazo a ese código. Así que voy a hacer exactamente el mismo truco
lo hicimos antes. No quiero b para los Retrocesos de Fibonacci. Voy a introducir un máximo de valores 0, lo que
tiene exactamente los mismos argumentos que val máx. Aquí voy a iniciar la nota a ser 0, o
estar vacío, más bien, el diccionario. Y a continuación, Voy a llamar a valores máximo rápido que pasa en este extra
argumento de la nota. Así que lo primero que voy a hacer es, estoy
va a tratar de devolver el valor de la nota. Esta es una buena cosa que hacer, Ęverdad? Si se trata de
no está ya allí, Ęqué pasará? Será lanzará una excepción. Y voy a ir a la excepción
cláusula. Así que estoy usando el Python pruebas, excepto para comprobar si o no lo es en el
nota o no. Trato de devolver el valor. Si que está ahí, me lo devuelva. Si no voy a tener una
error de clave. ĘY qué hago si me da una clave error? Bueno, ahora voy por el código mucho
como lo que hizo por valores máximo en el primer lugar. Puedo comprobar si es 0, et cetera, et cetera.
Es exactamente, en realidad, el mismo, sino ante Puedo devolver el valor que le he devuelto
ardilla lejos en mi nota para el futuro. Por lo que es la estructura misma de antes. Salvo,
antes de devolver el valor, que guardarlo. Así que el la próxima vez que lo necesito, puedo mirar hacia arriba.
Vamos a ver si funciona.
Bueno, vamos a hacer un pequeĄo ejemplo en primer lugar. Es llamando a los valores máximo de edad. Con todos los impresos
declaraciones. Lo siento. Pero vamos a dejar que ejecutarlo. Bueno, es un poco mejor. Es
tiene 85. La misma respuesta, pero pide 50 en lugar de 85 aĄos. Pero vamos a tratar de la grande. Debido a que
estamos muy valiente. Así que aquí es donde tenemos 30 elementos, y un peso máximo de 40. Yo no voy a llamar a los valores máx otros aquí
porque sabemos lo que sucede cuando hago eso. He creado mi propia nota de poco más de allí.
Y vamos a dale caĄa. Wow. Bueno, tuve la misma respuesta. Esa es una buena cosa. Y en su lugar
de 17 millones de llamadas, tengo 1.800 llamadas. Eso es una gran mejora. Y eso es una especie de
magia de la programación dinámica. El jueves vamos a hacer un análisis más cuidadoso
y tratar de entender cómo pude haber logrado esta tarea aparentemente mágica de la solución de un
problema de manera exponencial en poco tiempo.