Solución recursiva al problema del morral uno-cero
Contenido del curso
Johan Labrada
Jesus Alejandro Lechuga Ortega
Orlando Ramirez
JONATAN CADAVID TORRES
Fredy Alberto Orozco Loaiza
Reinaldo Orozco
Royer Guerrero Pinilla
Yerson Alexander Arredondo García
Maria Guadalupe Diaz Escobar
Manuel Alejandro Hermoso
Santiago Ahumada Lozano
Sergio Daniel Castañeda Pérez
Paolo Donato Torregrosa Navarro
David Aroesti
Profesor
Cesar Orozco Manotas
Alexis Otaño
Daniel Eishu Oyama Arevalo
María José Medina
Joel Eduardo Gaspar
Moisés Manuel Morín Hevia
Daniel Alejandro Moreno Astorga
Alexander Román
Sebastian CA
Vicente Fernandez
Moisés Manuel Morín Hevia
Cristopher Sahagún
Joaquin Fontela
Jose de Jesus Herrera Ledon
Luis Fernando Pedroza Taborda
Karl Behrens Gil
Sergio Mora
Jesús Enrique Morocoima Marcano
Mauricio Gonzalez Falcon
LUIS CALDERON
jorge rando hernandez
Gustavo Esquivel Sosa
Daniel Correa
Germán Danilo Forero Vargas
Alexander Moreno Córdoba
Mauricio Gonzalez Falcon
Oyarzabal Ivan
me tomé la tarea de mostrar gráficamente el problema de recursividad con los mismos valores del ejemplo del profesor, por si a alguien le ayuda a comprenderlo más fácil c:
Muy bueno, recorde que en la recursion los problemas resulven como arboles, asi que es muy claro el ejemplo, aun que me tomo unos momentos entenderlo
Excelente, realmente agradecido que te hayas tomado el tiempo de hacer este grafico.
Muy buena clase, David es un gran profesor. En esta oportunidad quiero dar un consejo con las clases complejas, en este caso algoritmos mas complejos como el problema del morral y ordenamiento por mezcla. El consejo es: Sean mas graficos. Llevar este problema a una version muy simple y explicar a mano en la tableta como se solucionarian. Si alguien vio el curso de introduccion a la programaciòn que dicta Freddy, cuando explica el algoritmo del cajero electronico(atm), el explica graficamente ese ejercicio y personalmente creo que seria muy dificil no entenderlo de esa forma.
Ahora si usted esta teniendo problemas para entender este algoritmo, no se desanime, hagalo a mano en una hoja, comprenda la logica y luego leer el codigo puede ser mas facil.
Lo ideal es que si, igual. También sería bueno que vayas cogiendo práctica en el mundo de los algoritmos, asi que pues si no entiendes un algoritmo leyéndolo, coja lápiz y papel y comiences a resolver todo, así lo vez con mayor claridad y entiendes más. Salu2
Totalmente de acuerdo, incluso se le haría un honor a la clase anterior a esta titulada ¿Porque graficar?, termine resolviéndolo a mano en una hoja y fue lo que en definitiva me ayudo a entenderlo.
Con platzi aprendiendo a ser ladrón profesional 🦝
Jajajajajaja
Jajajajajajaja
-------------------------------------------------- Calculo del problema del morall de forma recursiva * Analizamos Elemento 3 * - Espacio en morral = 30 - Peso = 30, valor = 120 -------------------------------------------------- --> SI Robo el elemento 3 y sumo a mi morral 120 en valor! * Analizamos Elemento 2 * - Espacio en morral = 0 - Peso = 20, valor = 100 Espacio en morral lleno! -------------------------------------------------- --> NO robo el elemento 3! * Analizamos Elemento 2 * - Espacio en morral = 30 - Peso = 20, valor = 100 -------------------------------------------------- --> SI Robo el elemento 2 y sumo a mi morral 100 en valor! * Analizamos Elemento 1 * - Espacio en morral = 10 - Peso = 10, valor = 60 -------------------------------------------------- --> SI Robo el elemento 1 y sumo a mi morral 60 en valor! * Analizamos Elemento 0 * - Espacio en morral = 0 - Peso = 30, valor = 120 Espacio en morral lleno! -------------------------------------------------- --> NO robo el elemento 1! * Analizamos Elemento 0 * - Espacio en morral = 10 - Peso = 30, valor = 120 Indice final alcanzado! -------------------------------------------------- --> NO robo el elemento 2! * Analizamos Elemento 1 * - Espacio en morral = 30 - Peso = 10, valor = 60 -------------------------------------------------- --> SI Robo el elemento 1 y sumo a mi morral 60 en valor! * Analizamos Elemento 0 * - Espacio en morral = 20 - Peso = 30, valor = 120 Indice final alcanzado! -------------------------------------------------- --> NO robo el elemento 1! * Analizamos Elemento 0 * - Espacio en morral = 30 - Peso = 30, valor = 120 Indice final alcanzado! * El metodo se llamo 9 veces para calcular 3 elementos El valor maximo que podemos robar es 160 La complejidad del algoritmo es O(nW) donde n es el numero de elementos y W el tamano del morral
Código con prints
contador = 0 """Complejidad algoritmica O(nW) donde n es el numero de elementos y W el tamano del morral""" def morral(tamano_morral, pesos, valores, n, mensaje): print('-' *50) print(mensaje) global contador contador += 1 print(f' * Analizamos Elemento {n} *') print(f' - Espacio en morral = {tamano_morral}') print(f' - Peso = {pesos[n - 1]}, valor = {valores[n - 1]} ') if n == 0 or tamano_morral == 0: if tamano_morral == 0: print(' Espacio en morral lleno!') elif n == 0: print(' Indice final alcanzado!') return 0 if pesos[n - 1] > tamano_morral: print(' peso del elemento > espacio morral...') return morral(tamano_morral, pesos, valores, n - 1, '') return max(valores[n - 1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1, f'--> SI Robo el elemento {n} y sumo a mi morral {valores[n - 1]} en valor!'), morral(tamano_morral, pesos, valores, n - 1, f'--> NO robo el elemento {n}!')) if __name__ == '__main__': valores = [60, 100, 120] pesos = [10, 20 ,30] tamano_morral = 30 n = len(valores) resultado = morral(tamano_morral, pesos, valores, n, 'Calculo del problema del morall de forma recursiva') print(f'\n * El metodo se llamo {contador} veces para calcular {n} elementos') print(f'El valor maximo que podemos robar es {resultado}') print('La complejidad del algoritmo es O(nW) donde n es el numero de elementos y W el tamano del morral')
Excelente trabajo!!!!
Esta muy bueno tu aporte, muchas gracias Manuel!
Este curso me motivo a retomar mis estudios independientes en computer science https://github.com/ForrestKnight/open-source-cs espero les sirva este recurso y se emocionen tanto como yo <3
Te puedo adelantar que estamos construyendo toda una escuela completa de Computer Science. Algortimos, Compiladores, Sistemas Operativos, Cómputo Paralelo, Arquitectura de cómputadras, etc. etc. Mi sueño es que los mejores computer scientists sean de latam :D
muy buen temario.
Como todo análisis hay que buscar los limites, cuando tiende a 0 (cuando el morral es muy chico) o cuando tiende a infinito (al morral le entra todo).
El primer caso se descarta por que para medir que tan complejo es se toma el valor mas grande, y este se da cuando a el morral le entra todo, de ahí para abajo:
Para ello hice la función dinámica, cambiando la cantidad de n en cada iteracion usando la generacion de listas que hicimos en las clases anteriores, y contando cuantas veces entraba, deduje que entra: (2 ** (n+1)) - 1 Y el numero da exacto así que esa es la dificultad o complejidad del algoritmo.
Aqui el codigo:
import random def contador(): global i i=i+1 return i def morral(tamano_morral, pesos, valores, n): contador() if n == 0 or tamano_morral == 0: return 0 if pesos[n-1] > tamano_morral: return morral(tamano_morral, pesos, valores, n-1) return max( valores[n-1] + morral(tamano_morral - pesos[n-1], pesos, valores, n-1), morral(tamano_morral, pesos, valores, n-1) ) if __name__ == '__main__': global i for j in range (1,15): valores = [random.randint(0, 100) for i in range(j)] pesos = [random.randint(0, 100) for i in range(j)] #valores = [1,2,3,4,60,100,120,20,30,450] #pesos = [5,10,15,20,10,20,30,11,15,5] tamano_morral = 10 * j n = len(valores) i = 0 resultado = morral(tamano_morral, pesos, valores, n) print('cuando N =',n, ' llama: ', i, '(2**(n+1)) - 1 = ',(2**(n+1)) - 1) print('el valor maximo seria: ',resultado)
y el resultado:
cuando N = 1 llama: 2 (2**(n+1)) - 1 = 3 cuando N = 2 llama: 4 (2**(n+1)) - 1 = 7 cuando N = 3 llama: 5 (2**(n+1)) - 1 = 15 cuando N = 4 llama: 8 (2**(n+1)) - 1 = 31 cuando N = 5 llama: 11 (2**(n+1)) - 1 = 63 cuando N = 6 llama: 14 (2**(n+1)) - 1 = 127 cuando N = 7 llama: 62 (2**(n+1)) - 1 = 255 cuando N = 8 llama: 57 (2**(n+1)) - 1 = 511 cuando N = 9 llama: 237 (2**(n+1)) - 1 = 1023 cuando N = 10 llama: 74 (2**(n+1)) - 1 = 2047 cuando N = 11 llama: 908 (2**(n+1)) - 1 = 4095 cuando N = 12 llama: 454 (2**(n+1)) - 1 = 8191 cuando N = 13 llama: 402 (2**(n+1)) - 1 = 16383 cuando N = 14 llama: 1330 (2**(n+1)) - 1 = 32767
Concuerdo con el análisis es (2**(n+1))-1 como máximo, ya que el algoritmo se puede saltar iteraciones dependiendo los datos.
Hola! que buen aporte. Podrias dejar algunas referencias de cómo hacer el cálculo exacto de la complejidad? Gracias :D
Estas últimas clases están muy mindblowing
Seeeee xD estan muy interesantes.
Al igual que lo del ordenamiento por mezcla debería estar mejor explicado. De alguna forma esquemática no se. Es difícil imaginarselo.
Exacto , aunque he investigado en yt sobre esto tambien
estoy de acuerdo, pienso que deberian de estar devididos en parte teorica, practica-teórica y practica, así todo es más facil y los conceptos se dan de una forma más amena
Siempre me ha costado entender la recursividad
A mi tmb pero cuandos entiende se gana.
No se preocupe compañero, a mí me tomó 5 años entenderla a la perfección :)
Parece ser similar a la funcion recursiva que calculaba fibonacci: puede ser O(2 ^ n)?
Una buena opción también es usar un diccionario, calculando la relación peso beneficio como llave, luego ordenar las llaves en una lista, usar esa lista para correr la función de llenar la mochila.
def weith_benefist(weight:int, profit:int)->float: return profit/weight def get_articles_dict(articles:list)->dict: articles_dict = dict() for article in articles: _weight = article.weight _profit = article.profit _profit_weight = weith_benefist(_weight , _profit ) articles_dict.update({ _profit_weight : { 'weight': _weight, 'profit':_profit } }) return articles_dict # Ahora podemos aplicar un algoritmo para el llenado de la mochila # Dando preferencia a los articulos que mas combienen def fill_bag(max_weight, articles_dict:dict)->list: # Esta linea nos da un orden por costo beneficio, lo vamos a usar para dar una primer salida valuated = sorted(articles_dict.keys(), reverse=True) # Y aquí se puede aplicar un algoritmo sin recursividad para mas de 3 objetos
j3su5pro, me parece otra buena solución con dicionarios lo que se aplico en el primer curso, gracias por el aporte.
https://github.com/karlbehrensg/poo-y-algoritmos-python El problema del morral
Imagina que eres un ladrón que entra a un museo pero tienes un gran problema, nada mas tienes una mochila pero hay muchísimas cosas mas de las que puedes cargar, por lo cual debes determinar cuales artículos puedes cargar y te entregaran el mayor valor posible.
Para este problema sabemos que no podemos dividir los artículos, por lo que nuestra primera aproximación sera evaluar los artículos.
def morral(tamano_morral, pesos, valores, n): if n == 0 or tamano_morral == 0: return 0 if pesos[n - 1] > tamano_morral: return morral(tamano_morral, pesos, valores, n - 1) return max(valores[n - 1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1), morral(tamano_morral, pesos, valores, n - 1)) if __name__ == '__main__': valores = [60, 100, 120] pesos = [10, 20, 30] tamano_morral = 40 n = len(valores) resultado = morral(tamano_morral, pesos, valores, n) print(resultado)
no entiendo porque en toda la funcion pone (n - 1) para referirse al elemento que esta evaluando y a la vez para el siguiente elemento :c * alquien que me ayude, gracias!!
Depende de como se construya el algoritmo se puede aplicar diferente con la misma finalidad en un ciclo for, pero en este caso también lo hace el profesor restando los indice así los If puedan ir iterando en cada paso hasta gastar toda la longitud de la lista
Hola! El profesor Utiliza N - 1 para hacer la función recursiva y leer los arrays del fin al principio.
Por ejemplo:
list = [1, 2, 3, 4] print(list[::-1]) # 4, 3, 2, 1
tengo que practicar bastante las funciones recursivas porque para nada entendi lo de las funciones recursivas....
no te voy a mentir no he entendido bien la resolución de este problema mañana lo mirare con mas detenimiento
Man, me dio un dolor de cabeza el solo pensar cuando llegue a mi casa y vea el oro molido, la plata molida y el arroz todos revueltos en la mochila. El trabajo que me va a costar separarlos. NO, si la vida de ladrón no es fácil...
Considero que la complejidad es de O(2**n), **n porque hay recursividad del codigo y el 2 porque al final de la funcion se le llama 2 veces, yo se que hay un if que tambien llama a la funcion pero como es un condicional, no lo tomo en cuenta porque me parece una "variacion pequeña"
La complejidad O(n) = 2**n
iteracion = 0 def morral(tamano_morral, pesos, valores, n): global iteracion iteracion += 1 print(f'Iteración {iteracion} probando con n={n}') if n == 0 or tamano_morral == 0: return 0 if pesos[n-1] > tamano_morral: return morral(tamano_morral, pesos, valores, n-1) return max(valores[n-1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1), morral(tamano_morral, pesos, valores, n-1)) def main(): global iteracion iteracion = 0 valores = [60, 100, 120] pesos = [10, 20, 30] tamano_morral = 50 n = len(valores) resultado = morral(tamano_morral, pesos, valores, n) print (resultado) if __name__ == "__main__": main()
Donde podría encontrar una mejor descripción de este problema?
Encontré este video que explica un caso de uso real, y muestra a detalle este mismo ejemplo: Youtube
Por si les cuesta entender el algoritmo, piensen que la segunda mitad del max() es la parte donde vuelve a sumar los elementos posibles que continuan, y vuelve a hacer lo mismo todo el tiempo, cuando se cierrran todos los frames queda algo asi "suma de los ultimos valores VS suma maxima de todas las posibles combinaciones (exceptuando la ultima suma porque esa ya esta hecha)" es que penso en esto es un genio completamente.
