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:


¿Qué es el problema del morral?
El problema del morral o "knapsack problem" es un desafío clásico en la programación y teoría de algoritmos. Imagina que eres un ladrón a punto de entrar a un museo o una casa. Tu dilema es que solo tienes una mochila en la cual llevarte los objetos de valor y estos objetos pesan más de lo que puedes acarrear. Debes decidir qué elementos llevar para obtener el mayor valor posible de tu botín. Este problema se convierte en una cuestión de optimización, que busca maximizar el valor total de los artículos que puedas "empaquetar" en la mochila, respetando un límite de peso.
En esta clase, nos concentramos en una variante específica conocida como "0-1 Knapsack Problem", que limita a las decisiones binarias: o tomas un artículo o lo dejas.
¿Cómo se puede resolver el problema del morral?
Algoritmos codiciosos
Un enfoque posible, aunque no idóneo para el 0-1 Knapsack, son los algoritmos codiciosos. Estos funcionan tomando primero los elementos de valor más alto o eficiencia antes que otros, llenando la mochila con el preciado "oro" antes de agregar la "plata" y, finalmente, el "arroz" como lastre. Los algoritmos codiciosos son efectivos donde los elementos pueden subdividirse; sin embargo, nuestro problema no permite tal flexibilidad.
Algoritmo recursivo
La solución implementada en esta clase emplea una función recursiva que evalúa cada caso posible:
max de Python para comparar los valores obtenidos al incluir o no un elemento, regresando el máximo alcanzable.Implementación del código en Python
A continuación, se detalla cómo se estructura este algoritmo:
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) ) valores = [60, 100, 120] pesos = [10, 20, 30] tamano_morral = 50 n = len(valores) resultado = morral(tamano_morral, pesos, valores, n) print(resultado)
¿Cómo analizar la complejidad algorítmica?
La complejidad algorítmica del problema del morral es esencial para entender su eficiencia. En el caso de este algoritmo recursivo, cada pieza del conjunto se resuelve aproximadamente dos veces, resultando en una complejidad de tiempo exponencial, O(2^n), donde n es el número de objetos. Esta característica hace que la variante recursiva básica sea ineficaz para grandes conjuntos de datos.
¿Por qué es importante dominar este problema?
El problema del morral no es solo un ejercicio académico; ofrece un paradigma que se aplica ampliamente en situaciones reales. Problemas de optimización similares surgen en logística, planificación de recursos y muchas áreas donde se maniobran restricciones o limitaciones físicas. Con una mejor comprensión y habilidad para identificar estos problemas, los desarrolladores pueden aplicar estos algoritmos para generar soluciones óptimas y eficientes.
¡Anímate a seguir explorando!, y recuerda que cada nuevo algoritmo que domines amplía tus herramientas para resolver problemas del mundo real.
El problema del morral o "knapsack problem" es un desafío clásico en la programación y teoría de algoritmos. Imagina que eres un ladrón a punto de entrar a un museo o una casa. Tu dilema es que solo tienes una mochila en la cual llevarte los objetos de valor y estos objetos pesan más de lo que puedes acarrear. Debes decidir qué elementos llevar para obtener el mayor valor posible de tu botín. Este problema se convierte en una cuestión de optimización, que busca maximizar el valor total de los artículos que puedas "empaquetar" en la mochila, respetando un límite de peso.
En esta clase, nos concentramos en una variante específica conocida como "0-1 Knapsack Problem", que limita a las decisiones binarias: o tomas un artículo o lo dejas.
Un enfoque posible, aunque no idóneo para el 0-1 Knapsack, son los algoritmos codiciosos. Estos funcionan tomando primero los elementos de valor más alto o eficiencia antes que otros, llenando la mochila con el preciado "oro" antes de agregar la "plata" y, finalmente, el "arroz" como lastre. Los algoritmos codiciosos son efectivos donde los elementos pueden subdividirse; sin embargo, nuestro problema no permite tal flexibilidad.
La solución implementada en esta clase emplea una función recursiva que evalúa cada caso posible:
max de Python para comparar los valores obtenidos al incluir o no un elemento, regresando el máximo alcanzable.A continuación, se detalla cómo se estructura este algoritmo:
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)
)
valores = [60, 100, 120]
pesos = [10, 20, 30]
tamano_morral = 50
n = len(valores)
resultado = morral(tamano_morral, pesos, valores, n)
print(resultado)
La complejidad algorítmica del problema del morral es esencial para entender su eficiencia. En el caso de este algoritmo recursivo, cada pieza del conjunto se resuelve aproximadamente dos veces, resultando en una complejidad de tiempo exponencial, O(2^n), donde n es el número de objetos. Esta característica hace que la variante recursiva básica sea ineficaz para grandes conjuntos de datos.
El problema del morral no es solo un ejercicio académico; ofrece un paradigma que se aplica ampliamente en situaciones reales. Problemas de optimización similares surgen en logística, planificación de recursos y muchas áreas donde se maniobran restricciones o limitaciones físicas. Con una mejor comprensión y habilidad para identificar estos problemas, los desarrolladores pueden aplicar estos algoritmos para generar soluciones óptimas y eficientes.
¡Anímate a seguir explorando!, y recuerda que cada nuevo algoritmo que domines amplía tus herramientas para resolver problemas del mundo real.
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 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.
Con platzi aprendiendo a ser ladrón profesional 🦝
--------------------------------------------------
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')
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
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
Estas últimas clases están muy mindblowing
Al igual que lo del ordenamiento por mezcla debería estar mejor explicado. De alguna forma esquemática no se. Es difícil imaginarselo.
Siempre me ha costado entender la recursividad
Parece ser similar a la funcion recursiva que calculaba fibonacci: puede ser O(2 ^ n)?
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
ProfesorCesar 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.