Problema de la mochila

A continuación vemos como resolver el problema de la suma de subconjuntos. Este problema consiste en lo siguiente.

• 🎒 Tienes una mochila de un determinado tamaño.
• 💻 🖊️ 📒 🧸 🔦 🩴 Y un conjunto de objetos donde cada uno ocupa un determinado volumen.

El problema que tenemos es que no podemos meter todo en la mochila. Queremos por tanto saber que opciones tenemos para optimizar la mochila al máximo.

Este algoritmo nos permite buscar que objetos puedes meter en tu mochila sin que quede espacio libre, dándonos todas las combinaciones posibles.

Existen múltiples variantes de este algoritmo. Vemos la más didáctica aunque no la más eficiente.

from itertools import combinations

def obtiene_combinaciones(objetos, mochila):
    result = []
    pesos = list(objetos.values())
    nombres = list(objetos.keys())

    for r in range(1, len(pesos) + 1):
        for s_i in combinations(range(len(pesos)), r):
            s_p = [pesos[i] for i in s_i]
            if sum(s_p) == mochila.get('🎒'):
                s_n = [nombres[i] for i in s_i]
                result.append(s_n)
    return result

Ahora damos unos valores a nuestros objetos. Estos indican lo que ocupa cada objeto en la mochila:

• 💻 Ordenador: 5
• 🖊 Boli: 1
• 📒 Libreta: 5
• 🧸 Peluche: 3
• 🔦 Linterna: 2
• 🩴 Chanclas: 4

Por otro lado tenemos la mochila, que tiene la siguiente capacidad.

• 🎒 Mochila: 14

Como puedes ver no entra todo en la mochila. Si sumamos lo que ocupan todos los objetos tendríamos 20 pero en la mochila solo entra 14.

Usando nuestra función obtiene_combinaciones obtenemos todas las combinaciones posibles de lo que podríamos llevar.

objetos = {'ordenador': 5,
           'boli': 1,
           'libreta': 5,
           'peluche': 3,
           'linterna': 2,
           'chanclas': 4}

mochila = 14

combinaciones = obtiene_combinaciones(objetos, mochila)
for i in combinaciones:
    print(i)

Estas son las combinaciones resultantes. Puedes comprobar que todas suman 14, la capacidad de la mochila:

• 💻📒🩴
• 💻🖊📒🧸
• 💻🧸🔦🩴
• 📒🧸🔦🩴

✏️ Ejercicios:

• Como puedes ver nuestro algoritmo es muy ineficiente. Busca una forma de optimizarlo. Dejamos para los usuarios más avanzados la opción de usar programación dinámica.
• Existe un problema parecido más completo llamado knapsack. Este nos permite tener en cuenta no sólo el tamaño de nuestros objetos sino su importancia. Si vamos a la playa, tal vez las chanclas sean más importantes. Este algoritmo nos permite introducir este concepto de importancia, asignando un peso a cada elemento. Implementa una nueva función que asigne una importancia a cada elemento y usa el algoritmo de knapsack para resolverlo.