El problema del morral

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 🦝

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 ❤️

--------------------------------------------------
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')

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

Siempre me ha costado entender la recursividad

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
		

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)

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()

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.

se coge otro morral y puedo cargar mas cosas 😃

Este es mi codigo, le agregue ingresar los datos por teclado y nos imprime el valor de n para poder observar como se comporta

def mochila(tamano_mochila, lista_pesos, lista_valores, n): #declaro todos los parametros
    print(f'n= {n}')
    print('------------------resultado nuevo--------------------')
    
    if n == 0 or tamano_mochila == 0: #si la lista de valores(n) es 0 o ya no hay espacio en la mochila entramos
         return 0
    if lista_pesos[n - 1] > tamano_mochila:
        return mochila(tamano_mochila, lista_pesos, lista_valores, n - 1)

    print(f'n= {n}')

    return max(lista_valores[n - 1] + mochila(tamano_mochila - lista_pesos[n-1], lista_pesos, lista_valores, n - 1),
              mochila(tamano_mochila, lista_pesos, lista_valores, n - 1))

if __name__ == '__main__':
        objetos = int(input('Ingrese la cantidad de objetos: '))
        lista_valores = []
        lista_pesos = []
        for x in range(objetos):
            valor = int(input('introduce el valor del objeto: '))
            pesos = int(input('Introduce el peso del objetos: '))
            lista_pesos.append(pesos)
            lista_valores.append(valor)
 
        tamano_mochila = int(input('Ingrese el tamaño de la mochila: '))
        
        n = len(lista_valores)

        resultado = mochila(tamano_mochila, lista_pesos, lista_valores, n)
        print(f'lista pesos {lista_pesos}')
        print('-' *50)
        print(f'lista de valores {lista_valores}')
        print('-' *50)
        print(f'tamaño mochila {tamano_mochila}')
        print('-' *50)
        print(f'El valor total que podemos juntar en la mochila es: {resultado}')```

La complejidad algorítmica es O(2**n).

A mi parecer la complejidad es 2**n, el análisis que hice parte del hecho de que por una entrada debo llamar dos veces la función, luego esas dos veces tengo que llamarla otras dos veces (en la segunda comparación sería 4)y así se iría hasta que llegase al caso base

Este curso fue increíble, lo voy a repetir como mínimo 3 veces mas. Muchas cosas interesante que en ningún otro lugar se aprenden.

Max nos permite escoger cuál es el valor máximo entre dos valores posibles.
Max es una función

def morral(tamano_morral, pesos, valores, n): #funcion con las variables donde agragamos la variable n la cual nos permite
    print(f'Tamaño del morral: {tamano_morral}, Peso: {pesos[n - 1]}, Valores: {valores[n - 1]}') # definir cual sera el indice en cual estamos trabajando.
    
    if n == 0 or tamano_morral == 0:       
        return 0

    if pesos[n - 1] > tamano_morral:        
        return morral(tamano_morral, pesos, valores, n -1)

    maximo = max(valores[n - 1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n -1),
                morral(tamano_morral, pesos, valores, n - 1))
    print(f'Maximo valor: {maximo}')
    return maximo

if __name__ == '__main__':
    valores = [60, 100, 120]
    pesos = [10, 20, 30]
    tamano_morral = 50
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)
    print(resultado)

Lo que hice fue obtener el valor máximo en una variable y luego imprimir cuál es el resultado junto con el peso y el valor relacionado. También imprimo el tamaño del morral para verificar como va reduciendo su tamaño.

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)

    maximum = max(valores[n - 1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1),
                morral(tamano_morral, pesos, valores, n - 1))

    print(f'El tamaño del morral es {tamano_morral}')

    print(f'El máximo es {maximum} con el valor {valores[n-1]} y el peso {pesos[n-1]}')

    return maximum


if __name__ == '__main__':
    valores = [60, 100, 120]
    pesos = [10, 20, 30]
    tamano_morral = 30
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)
    #print(resultado)

Agregue estos print statements para saber en que n estoy y para ver tambien como va el tamano de la mochila mientras va recorriendo el codigo.
Me parece que la complejidad algoritmica seria de O(2**n) ya que la funcion corre dos veces por cada vez que se llama y a la n ya que depende de la cantidad de objetos que se necesiten dentro de la mochila, de no ser asi por favor corregirme.

def morral(tamano_morral, pesos, valores, n):
    
    if n == 0 or tamano_morral == 0:
        return 0
    print(n)

    if pesos[n - 1] > tamano_morral:
        return morral(tamano_morral, pesos, valores, n - 1)
    print(tamano_morral)
    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 = 50
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)

    print(resultado)```

El Problema del Morral, también conocido como el “Problema de la Mochila” o “Knapsack Problem” en inglés, es un conocido problema de optimización combinatorial que involucra determinar la mejor combinación de objetos para incluir en un morral (mochila) limitado por capacidad, de manera que se maximice el valor total de los objetos llevados, sin exceder la capacidad del morral.

La formulación clásica del Problema del Morral es la siguiente:

Dado un conjunto de “n” objetos, cada uno con un valor “vi” y un peso “wi”, y un morral con capacidad “W”, ¿cómo podemos seleccionar una combinación de objetos para poner en el morral de manera que el valor total de los objetos incluidos sea máximo y el peso total no exceda la capacidad del morral?

El objetivo es encontrar la combinación óptima de objetos que maximice el valor total y cumpla con la restricción de capacidad del morral.

Existen varias variantes del Problema del Morral, incluyendo el “Problema del Morral 0-1” (0-1 Knapsack), donde se asume que cada objeto solo puede ser incluido una vez en el morral (no puede tomar fracciones de los objetos), y el “Problema del Morral Fraccionario” (Fractional Knapsack), donde se permite tomar fracciones de los objetos para llenar el morral.

El Problema del Morral es un problema NP-duro, lo que significa que no existe un algoritmo eficiente para resolverlo en todos los casos con un tiempo de ejecución polinomial. Sin embargo, existen algoritmos heurísticos y aproximados que pueden proporcionar soluciones cercanas al óptimo en tiempos razonables.

Uno de los enfoques más comunes para resolver el Problema del Morral 0-1 es a través de la programación dinámica, que permite encontrar una solución óptima en tiempo polinomial en ciertos casos, pero en general, la complejidad del algoritmo de programación dinámica sigue siendo exponencial.

El Problema del Morral es un interesante y desafiante problema de optimización combinatorial que tiene aplicaciones en áreas como la planificación de recursos, la optimización de recursos en proyectos, la asignación de recursos en logística y muchos otros campos donde se deben tomar decisiones sobre qué elementos incluir para maximizar un valor objetivo dentro de ciertas restricciones.

Explicación del código 💚👩‍🏫

La verdad me tomó un rato entender como funciona este código 😅, no fue hasta que tomé papel y lápiz que entendí como funcionaba, hubiese sido útil que el profesor explicara la lógica detrás del código, pero bueno igual fue entretenido 💪🧠, aquí les dejo mi explicación detallada:

#Nota 1: Al final explico la lógica del código
#Nota 2: Copia y pega esto es un lector de texto para que no te confundas

def morral(tamano_morral, pesos, valores, n):
    #n es el indice sobre el cual vamos a estar trabajando

    if n == 0 or tamano_morral == 0:
        return 0
    """esto nos servirá para impedir que el código siga en un bucle de recursiones infinitas, porque debido a que solo hay 3 elementos
    en este código, (por ejemplo), solo habrá máximo 4 iteraciones y en la cuarta llamada recursiva todos los resultados darán 0"""

    if pesos[n - 1] > tamano_morral:
        return morral(tamano_morral, pesos, valores, n - 1)
        # Si el objeto actual es demasiado grande para caber en la mochila, se omite y se pasa al siguiente objeto.

    return max(valores[n - 1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1),
                morral(tamano_morral, pesos, valores, n - 1))
    """En esta linea lo que hace max es escoger el máximo valor entre una de las dos opciones, como ves en el código, la primera opción
    es es escoger el valor del elemento que estamos "iterando" y lo sumamos a la función morral (cuyo resultado se da en valor
    de la cajita), pero también le restamos peso al morral (el peso disponible que tiene el morral) y seguimos iterando, 
    y la segunda opción es NO escoger el elemento actual y seguir con el siguiente elemento."""

if __name__ == '__main__':
    valores = [60, 100, 120]
    pesos = [10, 20, 30]
    tamano_morral = 50
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)
    print(resultado)

'''Toda la acción ocurre en la linea 16 y 17 (de este ESTE código sin modificar), según lo que yo entendí, Lo que hace el algoritmo
detras de cámaras es tomar elemento por elemento, comenzando por el último elemento de la lista hasta el primero elemento de la lista, 
y empezar a ramificar la operación de la función, sobretodo la más importante de la linea 17 y 18, es decir el algoritmo evalua todos 
los escenarios posibles suponiendo que el elemento que se está evaluando si "entro en la bolsa", pero no solo ramifica suponiendo que
si se "metió el elemento n-1 en la bolsa", también ramifica suponiendo que dicho elemento "no entró en la bolsa", 
y todas las ramificaciones parten de ahí, o sea, de la linea 18, de la linea que da por hecho que el elemento 
"no entró en la bolsa". Si ya sé, esta función es el doctor strange'''

"""Una cosa importante a tener en cuenta cuando se estudia recursividad es que cuando una función se llama a si misma, si el código está
bien hecho la recursividad no va a seguir eternamente porque en cada llamada se le dan parametros distintos a la función y se supone 
que alguien programó un caso en el que la función devuelva un resultado y no haga más recusión, así que no se alarmen pensando 
en que no tiene sentido la recursividad porque es infinita (fue un poco lo que me pasó a mi al principio), 
y segundo, es importante saber que cuando la función hace una llamada a si misma, no va a continuar con su propia ejecución hasta 
que no se haya ejecutado por completo la función a la que llamó, por lo tanto si una función se llama a si misma y genera una 
recursión de 5 funciones, la  función original no se va a resolver hasta que se resuelvan las 5 llamadas que generó al hacer 
una llamada a si misma"""

Las personas que hacen programación competitiva se darán cuenta que esto esta mal explicado y mal ejecutado pues en realidad no esta resolviendo el problema de optimización, ademas de que no te esta enseñando a optimizar ni el método que se usa.

Te dejo este vídeo para que aprendas el porque de la optimizacion
https://www.youtube.com/watch?v=IZHvQTx2bZ0&t=189s

Y este otro que te va a explicar de forma algorítmica, con una prueba de escritorio para que aprendas a computarlo

https://www.youtube.com/watch?v=fVrPwSkSo0I&t=1352s

Siempre es bueno usar un sólo return

def bag(bag_size, weights, valuables, n):
    take = 0
    # no hay ma's elementos que verificar
    if n == 0 or bag_size == 0:
        pass
    elif weights[n - 1] > bag_size: # Si el peso del elemento es mayor al tamaño del morral
        take = bag(bag_size, weights, valuables, n - 1) # Recorsivamente usamos la misma función pero en los valores anteriores
    else:
        # Regreso el valor máximo que puedo toamr para el morral
        take = max(
            valuables[n - 1] + bag(bag_size - weights[n - 1], weights, valuables, n - 1),
            bag(bag_size, weights, valuables, n - 1)
        )
    return take

if __name__ == "__main__":
    bag_size = 5
    valuables = [60, 100, 120]
    weights = [10, 20, 30]
    n = len(valuables) # iremos de mayor a menor

    result = bag(bag_size, weights, valuables, n)
    print(result)

Estos dos prints me ayudarona a entender el algortimo, justo antes del ultimo return.

El problema de la mochila es uno de los 21 problemas NP-completos de Richard Karp, establecidos por el informático teórico en un famoso artículo de 1972.1​ Ha sido intensamente estudiado desde mediados del siglo XX y se hace referencia a él en el año 1897, en un artículo de George Mathews Ballard.2​

Si bien la formulación del problema es sencilla, su resolución es más compleja. Algunos algoritmos existentes pueden resolverlo en la práctica para casos de un gran tamaño. Sin embargo, la estructura única del problema, y el hecho de que se presente como un subproblema de otros problemas más generales, lo convierten en un problema frecuente en la investigación de operaciones.

Abajo está mi solución al problema usando recursión… (antes de ver la clase claro xD)
He de decir que la recursión en python es muy ineficiente en términos de tiempo y memoria, por lo que es preferible evitarla, pero con fines educativos es bueno ver la solución recursiva… PD: aquí dejo el ejercicio si quieren probar a resolverlo en un juez online de programación competitiva https://atcoder.jp/contests/dp/tasks/dp_d

N, M = map(int, input().split())
weights = []
values = []
for i in range(N):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)
# Se puede usar {} en vez de [None]*(M+1), pero es menos eficiente.
mem = [[None]*(M+1) for i in range(N)]
 
 
def f(weight, i):
    if i == N:
        return 0
    if not mem[i][weight]:
        new_weight = weight + weights[i]
        if new_weight <= M:
            a = values[i] + f(new_weight, i+1)
        else:
            a = 0
        mem[i][weight] = max(a, f(weight, i+1))
    return mem[i][weight]
 
 
print(f(0, 0))

En la recursividad de este programa, por cada elemento se llaman a dos mas
Aquí le dejo mi aporte, empleando print() para que puedan entender de forma mas fácil. Nota: he cambiado algunos terminos.

# Algoritmo del morral se conoce como "Algoritmo Codicioso"
def morral(tamano_morral, masas, valores, n):
    print(tamano_morral, masas, valores, n)
    # PRIMER CASO BASE
    # Si la longitud de la lista es 0, o el tamaño del morral el 
    # 0 devuelvo el numero 0.

    if n == 0 or tamano_morral == 0:
        print('opc 1')
        return 0

    # SEGUNDO CASO BASE
    # Si la masa es mayor de la que 
    # puedo guardar, entonces, sigo con el siguiente elemento de la lista.
    if masas[n - 1] > tamano_morral:
        print('opc 2')
        return morral(tamano_morral, masas, valores, n - 1)

    print('opc 3')
    return max(valores[n - 1] + morral(tamano_morral - masas[n - 1], masas, valores, n - 1), 
                morral(tamano_morral, masas, valores, n - 1))


if __name__ == '__main__':
    valores = [60, 100, 120] # Valores en dolares
    masas = [10, 20, 30]
    tamano_morral = 30  # Tamaño del morral, cuantos kg de masa puede cargar
    n = len(valores)

    resultado = morral(tamano_morral, masas, valores, n)
    
    # retorna el valor maximo que podemos tener en nuestro morral segun su tamaño
    print(f'puedo cargar {resultado} dolares en metales preciosos')```

No muy eficiente este algoritmo, cuando david puso el morrar de 25, el algoritmo se fue por el de 20 haciendo asi 100 pero si escogiese 2 de 10 obtendría 120!!

Pero sigue siendo bueno para salir de apuros

O(n)

alguien sabe xq tengo este erro??

Mi código con prints y algunas modificaciones para entender un poco mejor como funciona el algoritmo:

def morral(tamano_morral, pesos, valores, n):
    
    print(f't_morral: {tamano_morral}, peso: {pesos[n-1]}, valor: {valores[n-1]}')

    if n == 0 or tamano_morral == 0:
        print('return 0')
        return 0

    if pesos[n - 1] > tamano_morral:
        print('return morral')
        return morral(tamano_morral, pesos, valores, n - 1)    
    
    valor_1 = valores[n - 1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1)
    valor_2 = morral(tamano_morral, pesos, valores, n - 1)
    print(f'Valor 1: {valor_1}, Valor 2: {valor_2}')
    
    maximo = max(valores[n - 1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1),
    morral(tamano_morral, pesos, valores, n - 1))

    print(f'valor maximo: {maximo}')
    print('return max')
    return maximo



if __name__ == "__main__":
    valores = [60, 100, 120]
    pesos = [10, 20, 30]
    tamano_morral = 20
    n = len(valores)
    
    resultado = morral(tamano_morral, pesos, valores, n)
    print(resultado)
    ```

También considero que es exponencial O(2**n) porque siempre llama recursivamente a la función 2 veces. El tercerr llamado es opcional por un if y no se da en muchos casos.

Hola disculpa me quedo una duda con respecto al algoritmo, si debe de dar el mayor valor posible a almacenar, entonces cuando escoge el de 20 por sobre el de 10 funciona mal, ya que aunque el valor del de 20 es mayor a 10, se pueden escoger dos elementos con peso de 10 y así el valor máximo sobrepasaría al de 20. Tal vez solo entendí mal el problema pero quería expresar mi duda.

La complejidad es de 2**n al parecer

#Este es mi aporte del reto

class Bag:

def __init__(self,weights,values,n):
    self.weights = weights
    self.values = values
    self.n = n

def fill(self,size):
    if self.n==0 or size==0:
        return 0

    original = self.n
    self.n -= 1
    print(f'Size: {size}',f'n: {original}',f'weight={self.weights[self.n]}',f'n-1={self.n}',f'value_n-1={self.values[self.n]}')

    if self.weights[self.n]>size:
        return self.fill(size)

    x1 = self.values[self.n] + self.fill(size - self.weights[self.n])
    x2 = self.fill(size)

    print(f'x1={x1},x2={x2}')
    maximum = max(x1,x2)
    print(f'max={maximum}')
    return maximum

class Program:

def run(self):
    values = [60,100,120]
    weights = [10,20,30]
    n = len(values)
    size = self.getSize()
    bag = Bag(weights,values,n)
    result = bag.fill(size)
    print(result)

def getSize(self):
    try:
        size = int(input("Type the bag size: "))
        assert 0 <= size, "The size must be greater than 0"
        return size
    except:
        print("El valor ingresado no es un número")

if name==‘main’:
program = Program()
program.run()

 clase BagObject:
    def __init __ (self, weight, value, index):
        self.index = índice
        self.weight = peso
        self.value = valor
        self.report = valor // peso
  #Función para la comparación entre dos BagObjects
  # Comparamos el ratio calculado para ordenarlos
    def __lt __ (yo, otro):
        volver self.report & lt; otro.informe


def getMaxValue (peso, valores, capacidad):
        arraySort = []
        para i en rango (len (peso)):
            arraySort.append (BagObject (peso [i], valores [i], i))

        #Ordena los elementos de la bolsa por su informe
        arraySort.sort (reverse = True)

        counterValue = 0
        para el objeto en arraySort:
            currentWeight = int (object.weight)
            currentValue = int (object.value)
            si capacidad - peso actual> = 0:
                # agregamos el objeto en la bolsa
                # Restamos la capacidad
                capacidad - = peso actual
                counterValue + = currentValue
                # Agregamos el valor en la bolsa
        return counterValue


peso = [1,5,3,2,4]
valores = [10,50,20,30,60]
capacidad = 11
maxValue = getMaxValue (peso, valores, capacidad)
print ("Valor máximo en la mochila =", maxValue) 

He hecho mi código pasándole unas variables extras a la function de sack, para ver cómo le esta llendo en su recursividad.
Su complejidad creo que es O(n ** 2) ya que tiene que ser llamado recursivamente dos veces por cada resultado del valor total robado.

""" O(n) * O(n) = O(n ** 2)
"""

def sack (capacity, objs, num, status="initial", sum_money=0, items_taken=""):
    print(f"Capacity: {capacity}, iteration: {num}, status: {status}, sum_money: {sum_money}, items_taken: {items_taken}")

    # No more Items or Sack Full
    if num == 0 or capacity == 0:
        print(f"Capacity: empty or Last item")
        return 0

    if objs[num - 1][0] > capacity:
        print("Obj weights more than available")
        return sack(capacity, objs, num - 1, "weights more")

    return max(
        objs[num - 1][1] + sack(capacity - objs[num - 1][0], objs, num - 1, f"takes the item {num - 1}", sum_money + objs[num - 1][1], items_taken + f"{num - 1}"), 
        sack(capacity, objs, num - 1, f"doesnt take the item {num - 1}", sum_money, items_taken)
    )

if __name__ == "__main__":
    objs_to_steal = [
        # [weight, value]
        [10, 60],
        [20, 100],
        [30, 120]
    ]
    sack_capacity = 50
    num_items = len(objs_to_steal)

    best_item_combination = sack(sack_capacity, objs_to_steal, num_items)
    print(f"Best Result: {best_item_combination}")

Añadí estos print para guiarme en el código
creo que la complejidad seria # O(2**n)

def morral(tamano_morral, pesos, valores, n): # O(2**n)
    print('-' * 50)
    print(f'n = {n}  tamano_morral {tamano_morral}')
    #caso base 
    if n == 0 or tamano_morral == 0:
        print('Ya no hay espacio en la mochila!')
        return 0

    print(f'pesos[ n -1 ] {pesos[ n -1 ] }')
    if pesos[ n -1 ] > tamano_morral:
        return morral(tamano_morral, pesos, valores, n-1)

    print('Evaluamos para tomar el maximo')
    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 = 25 
    print(f"tamano del morral inicial: {tamano_morral}")
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)
    print(resultado)

Cada que llamamos a la función volvemos a llamar a la función 1 o 2 veces, eso significa que nuestra complejidad, con una lista infinita de pesos y de valores en el caso en el que siempre podamos escoger si agarrar o no agarrar el objeto crece exponencialmente como 2^n, es decir:
O(2^n) 😃 creo… jaja

Si no entienden como funciona max() aún, pueden ver esto: https://www.programiz.com/python-programming/methods/built-in/max

Lo explican muy bien, le dan 3 usos y ponen ejemplos

Hola, listo igual me gustaría tener un print después del return max…

#esto es programacion dinamica 
def morral(tamano_morral, pesos, valores, n): #n es el indice en el cual vamos a estar trabajando
    #si n==0 ya no se puede obetener mas eleementos
    if n == 0 or tamano_morral == 0: #este if a entregar la combinacion maxima de valores que puede tener
        return 0 #no se puede obtener mas

    if pesos[n - 1] > tamano_morral:
        return morral(tamano_morral, pesos, valores, n - 1) #funcion recursiva, vuelve a llamar el morral
        #se va al indice anterior
    print(pesos, ' | ', tamano_morral,  ' | ', valores, ' | ', n)
    print('-'*50)
    return max(valores[n - 1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1),
                morral(tamano_morral, pesos, valores, n - 1))
    #es el valor maximo entre los valores 

if __name__ == '__main__':
    valores = [60, 100, 120]
    pesos = [10, 20, 30]
    tamano_morral =int(input('ingrese el tamaño del morral: ')) #
    n = len(valores) #es el tamño de los valores

    resultado = morral(tamano_morral, pesos, valores, n)
    print(resultado)

Si eres de las personas que como a mi se les dificultó entender como se usaba la recursividad en este código aquí se las explico (por cierto, la idea inicial fue de @Joham Lebrada, así que creditos a le. También le implementé otras cosas y el arbol es más corto para que sea más facil de enteder y también incluí frames):

Codigo:

def knapsack(n, capacity):
	global iterations
	iterations += 1
	print(f"iteration {iterations} trying with n = {n}")
	if n == 0 or capacity == 0:
		return 0
	elif weight[n-1] > capacity:
		return knapsack(n-1, capacity = capacity)
	else:	#add it or not
		tmp_1 = knapsack(n - 1,capacity = capacity)
		tmp_2 = values[n-1] + knapsack(n-1, capacity - weight[n-1])
		return max(tmp_1, tmp_2)

#elemnts
weight = [2, 5, 1]
values = [10, 15, 20]#$


#knapsack
capacity = 15	#knapsack size
iterations = 0
n = len(values)	#indexes

result = knapsack(n = n, capacity = capacity)
print(f"with a knapsack that can carry only {capacity}kg, you can only add elemnts equivalent to {result}$\n\t{capacity}kg can carry {result}$")

print()
print(f"total iterations = {iterations}")

Recursividad implementada:

Frames globales generados + output (reducido):

Output final:

iteration 1 trying with n = 3
iteration 2 trying with n = 2
iteration 3 trying with n = 1
iteration 4 trying with n = 0
iteration 5 trying with n = 0
iteration 6 trying with n = 1
iteration 7 trying with n = 0
iteration 8 trying with n = 0
iteration 9 trying with n = 2
iteration 10 trying with n = 1
iteration 11 trying with n = 0
iteration 12 trying with n = 0
iteration 13 trying with n = 1
iteration 14 trying with n = 0
iteration 15 trying with n = 0
with a knapsack that can carry only 15kg, you can only add elemnts equivalent to 45$
	15kg can carry 45$

total iterations = 15

No logré ajustar el print statment para que me vaya mostrando el valor de “morral” en cada iteración. Seguiré cacharreando mañana el código.

La función resursiva se llama como máximo O(2^n) si mi estimación es correcta 😕

Saben donde puedo encontrar problemas imilares o el nombre para buscarlos y practicar más?

La complejidad algorítmica de este algoritmo es exponencial (O(2^n)), lo que significa que no es eficiente para problemas con un gran número de elementos. Para tamaños de entrada más grandes, el tiempo de ejecución aumenta de manera significativa, lo que hace que este algoritmo sea impráctico en esos casos.

import random

def backpack(pack_size, weight, value, n):

    if n == 0 or pack_size == 0:
        return 0
    if weight[n-1] > pack_size:
        return backpack(pack_size, weight, value, n-1)
    else:
        return max(value[n-1] + backpack(pack_size-weight[n-1], weight, value, n-1), 
                   backpack(pack_size, weight, value, n-1))


if __name__ == '__main__':
    value = random.sample(range(1, 1000), 7)
    weight = random.sample(range(1, 50), 7)
    print(f'Weight => {weight}', '/' * 5, f'Value => {value}')
    pack_size = int(input('Enter the pack size: '))
    n = len(value)

    result = backpack(pack_size, weight, value, n)
    print(f'Maximum value: {result}')

max es una funcion de python que nos permite escojer el valor mas grande dentro de dos valores posibles

Excelente hay mucho que profundizar

def morral(tamano_morral, pesos, valores, n):
    print("pesos_1 = ", pesos[n-1])
    print("valores = ", valores[n - 1])
    if n == 0 or tamano_morral == 0:#Caso base. Si el espacio vacio en la mochila es cero
        print("Entrando en if_1")
        print("n = ", n, "tamaño de morral = ", tamano_morral, "n es igual a 0 , retornando 0")
        return 0

    if pesos[n - 1] > tamano_morral:# Si el peso es mayor que el tamaño del morral , revisamos el objeto sig
        print("entrando en el if_2")
        print("peso = ",pesos[n-1], "tamaño del morral = ",tamano_morral)
        print("-"*10)
        print(f"{pesos[n - 1]} es mayor que  {tamano_morral} probando con el siguiente valor")
    
        return morral(tamano_morral, pesos, valores, n - 1)
    

        
             #Aqui se escoje un objeto en el morral 
             #Luego se vuelve a llamar la funcion pero sin el peso ya seleccionado
          #Aqui se toma un valor que quepa en la mochila y seguimos llamando a la funcion para seguir llamando la mochila
          #Se compara con la situacion de no haberlo tomado
    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 = 15
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)
    print("resultado = ", resultado)

<
**print("a")
**
def morral(tamano_morral, pesos, valores, n):
**    print("b")
**    if n == 0 or tamano_morral == 0:
**        print("c")
**        return 0
    if pesos[n -1] > tamano_morral:
       ** print("d")**
        return morral(tamano_morral, pesos, valores, n - 1)
**    print("e")
**    
    
    
    return max(valores[n - 1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1),
            morral(tamano_morral, pesos, valores, n - 1))
**    print("f")
**
if __name__ == '__main__':
    valores = [60, 100, 120]
    pesos = [10, 20, 30]
    tamano_morral = 50
    n = len(valores)> 

def morral(tamaño_morral, pesos, valores, n):
    
    if n == 0 or tamaño_morral == 0:
        return 0
    
    if pesos[n - 1] > tamaño_morral:
        return morral(tamaño_morral, pesos, valores, n-1)

    return max(valores[n-1] + morral(tamaño_morral- pesos[n-1], pesos, valores, n-1), morral(tamaño_morral, pesos, valores, n-1))

if __name__ == "__main__":
    valores = [60, 100, 120]
    pesos = [10, 20, 30]
    tamaño_morral = 60
    n = len(valores)

    resultado = morral(tamaño_morral, pesos, valores, n)
    print(resultado)

En el peor de los casos, la función crece en 2**n

Agrege que la variable tamano_morral, no fuera fija y entiendieras lo que significa el resultado

#Algoritmo del morral, se conoce como Algoritmo Codisioso

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 = int(input("¿Cuales el tamaño del morral?: "))
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)
    print(f"Al morral le entran: {resultado} kg")

def morral(tamaño,pesos,valores,index):
    if index==0 or tamaño==0:
        return 0

    if pesos[index-1]>tamaño:
        return morral(tamaño,pesos,valores,index-1)

    print(f"espacio restante {tamaño} valores en morral {valores[index-1]}")

    return max(valores[index-1]+morral(tamaño-pesos[index-1],pesos, valores, index-1), 
                morral(tamaño,pesos,valores,index-1))


if __name__=="__main__":
    valores=[60,100,120]
    pesos = [10,20,30]
    tamaño=50
    index=len(valores)

    resultado=morral(tamaño,pesos,valores,index)
    print(resultado)

Estupenda clase.

Explicacion mas detallada del problema propuesto en clase.

# Algoritmo del morral se conoce como "Algoritmo Codicioso"
def morral(tamano_morral, masas, valores, n):
    print(f'Se ejecuto la funcion morral, valores: {tamano_morral, masas, valores, n}')
    # PRIMER CASO BASE
    # Si la longitud de la lista es 0, o el tamaño del morral el 
    # 0 devuelvo el numero 0.

    if n == 0 or tamano_morral == 0:
        print('opc 1\n')
        return 0

    # SEGUNDO CASO BASE
    # Si la masa es mayor de la que 
    # puedo guardar, entonces, sigo con el siguiente elemento de la lista.
    if masas[n - 1] > tamano_morral:
        print('opc 2\n')
        return morral(tamano_morral, masas, valores, n - 1)

    print('opc 3\n')
    return max(valores[n - 1] + morral(tamano_morral - masas[n - 1], masas, valores, n - 1), 
                morral(tamano_morral, masas, valores, n - 1))


if __name__ == '__main__':
    valores = [60, 100, 120] # Valores en dolares
    masas = [10, 20, 30]
    tamano_morral = 30  # Tamaño del morral, cuantos kg de masa puede cargar
    n = len(valores)

    resultado = morral(tamano_morral, masas, valores, n)
    
    # retorna el valor maximo que podemos tener en nuestro morral segun su tamaño
    print(f'puedo cargar {resultado} dolares en metales preciosos')
    print('Falta ver donde se pueden vender')
    print('Pagare una subscripcion anual a platzi, ya que me alcanza')

Para entender como devuelve una combinacion u otra de las que realizo con recursividad, se debe entender que en el return, todo esta dentro de la funcion max(), asi que la recursividad en si misma va a comparar con la funcion max() los dos valores mas altos y va a retornar siempre la combinacion mas alta. hasta que vuelva a la primera capa de la funcion que fue la primera que ejecutamos y devuelva el mayor valor.

****–> NO robo el elemento 1!

• Analizamos Elemento 0 *

• Espacio en morral = 100
• Peso = 50, valor = 320
  Indice final alcanzado!

• El metodo se llamo 14 veces para calcular 3 elementos
  El valor maximo que podemos robar es 2120
  La complejidad del algoritmo es O(nW) donde n es el numero de elementos y W el tamano del morral
  jhonftb3@JFTB:/mnt/c/Users/user/Documents/poo_algor_python$ ****

hola, queria aportar al grupo dando una observacion al codigo, ya que el morral cuando el tamaño es 50. el maximo que puede obtener no seria 220, sino 300. dejo mi codigo para que lo revisen:

def morral(tamano_morral, pesos, valores, n): #funcion
    print(f'Tamaño del morral: {tamano_morral}, Peso: {pesos[n - 1]}, Valores: {valores[n - 1]}') # definir cual sera el indice en cual estamos trabajando.
    
    if n == 0 or tamano_morral == 0:       
        return 0

    if pesos[n - 1] > tamano_morral:        
        return morral(tamano_morral, pesos, valores, n -1)

    maximo = max(valores[n - 1] + morral(tamano_morral - pesos[n-1], pesos, valores, n),
                morral(tamano_morral, pesos, valores, n - 1))
    print(f'Maximo valor: {maximo}')
    return maximo

if __name__ == '__main__':
    valores = [60, 100, 120]
    pesos = [10, 20, 30]
    tamano_morral = 50
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)
    print(resultado)

A mi entender, este algoritmo explora todas las posibles combinaciones por lo que su complejidad es O(2^n), ya que el número de llamadas a la función recursiva es [2^(n + 1) - 1]

Entendí el problema del morral, pero no el código 😦

Utilicé el código de abajo para poder ver cuantos prints salian en un caso de 1 elemento, 2 elementos, 3 elementos, 4 elementos y 5 elementos (sin contar el print del resultado). El peor caso es en el cual la suma de los elemenots no supera el peso permitido de la mochila, así el algoritmo necesita evaluar todas las opciones siendo el peor de los casos.

def morral(tamano_morral, pesos, valores, n):
        
    if n == 0 or tamano_morral == 0:
        print('Case null')
        return 0
    
    if pesos[n - 1] > tamano_morral:
        print('Case overweight')
        return morral(tamano_morral, pesos, valores, n - 1)

    print(n)
    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] #[60, 60] [60, 60, 60] [60, 60, 60, 60] [60, 60, 60, 60, 60]
    pesos = [10] #[10, 10] [10, 10, 10] [10, 10, 10, 10] [10, 10, 10, 10, 10]
    tamano_morral = 50
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)
    print(resultado)

El resultado fue 3, 7, 15, 31, y 63 prints para cada unos de los casos. Con estos valores trate de obtener una función que relacionara el numero de elementos n y obtuve 4 * (2 ** (n - 1)) - 1. Por lo tanto en mi caso obtuve que O(2**n), lo cual se podría esperar debido a la doble recursividad en la línea de código

    return max(valores[n -1] + morral(tamano_morral - pesos[n - 1], pesos, valores, n - 1), morral(tamano_morral, pesos, valores, n - 1))

La utilización de un algoritmo voraz consiste en introducir en la mochila según orden decreciente de utilidad (beneficio) los diversos objetos. En una primera etapa, se adicionarán unidades enteras hasta que, por motivo de capacidad, no sea posible seguir introduciendo enteros y haya que añadir la porción que quepa del siguiente objeto.

b) Concepto de solución óptima:

Teorema: si se ordenan los objetos de forma decreciente en cuanto a su relación (utilidad/ponderación = bi/ci), y se introducen en la mochila enteros en este orden mientras quepan, y cuando no quede capacidad para uno entero se añade la porción que aún tenga cabida, el resultado al que se llega es una solución óptima.

Este problema se ha resuelto tradicionalmente mediante programación lineal entera.

El hecho de que se trate de programación lineal hace referencia a que la función a optimizar y las inecuaciones que constituyen las restricciones han de ser lineales, es decir, han de ser funciones cuyas incógnitas estén elevadas exclusivamente a la unidad.

Existe otra forma de resolver este tipo de problema, a través de los denominados algoritmos voraces. Una aproximación voraz consiste en que cada elemento a considerar se evalúa una única vez, siendo descartado o seleccionado, de tal forma que si es seleccionado forma parte de la solución, y si es descartado, no forma parte de la solución ni volverá a ser considerado para la misma. Con este método no siempre es posible dar una solución a un problema.

Otro sistema para resolver el problema de la mochila es mediante algoritmos genéticos que son métodos de optimización que tratan de hallar {\displaystyle (x_{i},\ldots ,x_{n})}{\displaystyle (x_{i},\ldots ,x_{n})} tales que sea máximo

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)

def morral(tamano_morral, pesos, valores, n):

    print(f"tamano_morral: {tamano_morral}, 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))

y diría que su complejidad algoritmica es O(3^n)

Yo agarré por practica y decidí ordenar las listas por el peso, y pasarlas en ese orden
A su vez hace una validación de que el tamaño de ambas listas sea igual.

"""This is an example of how to solve the 0-1 knapsack problem
    Also some sorting will be added to grab the items ordered by weight"""

def backpack(size_backpack, weights, values, n):
    #print(size_backpack, weights, values, n)

    #The following if is our base case, no more values or the backpack is full
    if n == 0 or size_backpack == 0:
        return 0

    #Other base case is that the element i want to include in the backpack is bigger than the backpack
    if weights[n - 1] > size_backpack:
        return backpack(size_backpack, weights, values, n-1)

    #masx function return the max values between 2 possible values
    #First part inside max() is what happen if i select the item, the second part is what happen if i do not select the item
    return max(values[n-1] + backpack(size_backpack - weights[n-1], weights, values, n-1), 
        backpack(size_backpack, weights, values, n-1))


def sort_lists(weights, values):
    #Merge the 2 lists into one
    zipped_pairs = dict(zip(weights, values))
    
    #obtaining the key(weights) of the zipped list
    zipped_pairs_items = zipped_pairs.items()

    #sort based on the keys (weights)
    sorted_zipped_pair = sorted(zipped_pairs_items)
     
    return sorted_zipped_pair


if __name__ == '__main__':

    n_values = int(input('Enter the number of elements on the value list: '))
    values = list(map(int,input('\nEnter the values, separate by a whitspace: ').strip().split()))[:n_values]
    
    print('\n\n*************\n\n')

    n_weights = int(input('Enter the number of elements on the weights list: '))
    
    if n_weights == n_values:
        weights = list(map(int,input('\nEnter the weight values (Kg), separate by a whitspace: ').strip().split()))[:n_weights]
    else:
        print('The amout of values must be the same as the amount of weights')

    #For this example i am going to treat the size backpack as a constant
    size_backpack = int(input('\nEnter the initial value for size of the backpack(Kg): '))

    n = len(values)

    #This will sort the weights so they can be grabbed in order
    sort_list_result = sort_lists(weights, values)
    print('\nOrdering the Values' + str(sort_list_result))

    #This will separate again the weights and values on 2 lists but ordered 
    sort_list_result = dict(sort_list_result)
    weights, values = zip(*sort_list_result.items())

    #Execution ...
    result = backpack(size_backpack, weights, values, n)
    print('\nThe maximum value that you can grab is: ' + str(result))

🤯

👍👍👍

A la hora querer usar la recursividad, tenemos que tener en mente el caso base.

Un greedy algorithm, siempre busca el valor más alto.

The Knapsack problem, también se puede resolver con greedy algorithms, osea algoritmos codiciosos.

Lo que significa el 01 del algoritmo, se refiere a tomar o no tomar

Hay muchas formas de resolver The Knapsack problem, pero existe uno bien bueno que es el 01 Knapsack, bastante sencillo.

El problema del morral o The knapsack problem: Eres un ladrón que entra en un museo, pero solo tiene una mochila para cargar las cosas, por lo que, no puedes llevarte tooo. El morral tiene un límite, así que tienes que escoger bien lo quieres hacer, para llevarte el mayor valor posible.

El problema de la mochila del algoritmo de Python es un problema de optimización, es decir, una función que debe maximizarse o minimizarse y restricciones que deben cumplirse.

Eso y parte de lo que hablaste en el video anterior es un problema de programación lineal(es matemáticas, busquen un libro de investigación de operaciones o busquen en YouTube.). Hay muchas aplicaciones, como por ejemplo, los pollos de una granja deben tener una cierta dieta diaria en gramos de carbohidratos, proteínas y grasas, entonces se les prepara una dieta con el mínimo gasto de $$ y satisfaciendo las necesidades nutricionales del animal.

Estoy como loco con los algoritmos que utilizan recursividad, me parecen una maravilla, los veo y los repaso y hago mis pruebas, para dominar la recursividad es la mejor forma de entenderlo.

Mas cursos sobre algoritmos porfavor!

Continuación.

Al principio pensé que era O(n^2)
Pero despues de leer un poco los aportes tiene bastante sentido que sea O(2^n) ya que llama 2 llamadas recursivas en n
Espero estar bien jeje

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)
    print(f"valores = {valores[n-1]} Peso = {pesos[n-1]}")
    print(f"tamaño del morral = {tamano_morral}")
    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] #Cuanto vale en dolares por ejemplo
    pesos = [10,20,30] #Cuanto vale en Kilo Gramos por ejemplo
    tamano_morral = 60 #Esta es la limitante
    n = len(valores)

    resultado = morral(tamano_morral, pesos, valores, n)
    print(resultado)

Viva México manito!

Tal vez me equivoque completamente, pero me parece que es O(nlog(n)). Este es mi razonamiento: en la primera recursión se compara de manera líneal si los objetos caben o no en el morral, siempre se debe hacer, de ahí la primera n. En la segunda recurrsión, si el objeto cabe en el morral, el tamaño del mismo se reduce, al igual que el problema. Ahora del porque a mí parecer es nlog(n) y no n + log(n). Porque las recursiones están en la misma función , por lo que su relación no es de secuencia (+) una despues de la otra. Sino que para ejecutar log(n) se debe ejecutar n, de ahí (n*log(n)).

Si me equivoco, por favor haganmelo saber.

Por la recursividad sería de complejidad exponencial, ¿verdad?

Excelente

Así quedó el mío c:

/* El problema del morral nos plantea que tenemos un morral en donde
debemos meter todos los objetos posibles sin pasar la capacidad del morral
generando el máximo valor posible dentro */

# Primero definimos nuestra función
def morral(morral_tam, pesos, valores, n):
	# Ahora comprobamos que no se nos hayan acabado los objetos o el tamaño del morral
	if n == 0 or morral_tam == 0:
		return 0

	# Aquí paramos si el peso excede el tamaño del morral 
	if pesos[n - 1] > morral_tam:
		return morral(morral_tam, pesos, valores, n - 1)

	# Tomamos una decision, si lo metemos agarramos la suma de los valores y se ejecuta la recursividad
	# Si no lo escogemos se pasa al siguiente objeto
	return max(valores[n - 1] + morral(morral_tam - pesos[n - 1], pesos, valores, n - 1),
			   morral(morral_tam, pesos, valores, n - 1))




if __name__ == '__main__':
	# Definimos el tamaño y asignamos los valores por un input para el usuario
	tam_valores = int(input('Ingrese el número de valores que va a introducir: '))
	print('El peso máximo que puede ocupar el morral es de 50\n')
	valores = []
	pesos = []
	morral_tam = 50

	for i in range(tam_valores):
		valores.append(int(input(f'Ingrese el valor del objeto {i + 1}: ')))
		pesos.append(int(input(f'Ingrese el peso del objeto {i + 1}: ')))
		print('\n')

	n = len(valores)

	# Llamamos y mostramos el resultado
	resultado = morral(morral_tam, pesos, valores, n)
	print('El valor máximo es de', resultado)```

Entendí la lógica por completo!! … todo juega con el orden de pesos.

Es complejo seguirle el paso a la recursividad: puse los siguientes prints para entender que pasaba:

def morral(capacidad_morral, pesos, valores, n):
    if n == 0 or capacidad_morral == 0:
        return 0

    if pesos[n-1] > capacidad_morral:
        return morral(capacidad_morral, pesos, valores, n-1)

    print('-'*50)
    print(f'2Capacidad: {capacidad_morral}')
    print(f'2Valores: {valores} - Pesos: {pesos} - {n}')
    print(f'2Data: {valores[n - 1]} {pesos[n - 1]}')

    maximo = max(valores[n - 1] + morral(capacidad_morral - pesos[n - 1], pesos, valores, n - 1), morral(capacidad_morral, pesos, valores, n-1))
    print(f'Maximo: {maximo}')
 
    return maximo

if __name__ == "__main__":
    valores = [60, 115, 80]
    pesos = [10,30,20]
    capacidad_morral = 30
    n = len(valores)

    resultado = morral(capacidad_morral, pesos, valores, n)
    print(resultado)

puede ser que llamemos 2 veces a la función recursiva por cada vez que se ejecuta?

No habría sido mejor crear un diccionario y enviarlo como parámetro a la función morral?