24

Estoy trabajando con un caso de un cliente en que aplica usar el algoritmo Problema de la mochila. Estoy utilizando el código que adjunto, funciona más o menos y tiene errores.

El ejemplo cuenta con 12 paquetes de diferentes pesos (que en su total pesan 1260 Kilos) con un valor o precio asociado. El objetivo es cargar la máxima cantidad de paquetes, priorizando los de mayor valor sin sobrepasar la carga máxima del camión.

Por ejemplo;

1.- Si la carga máxima del camión es de 9 Kilos, este código debería seleccionar Paquete 2 Peso :9 valor :160 y no Paquete 2 Peso :9 valor :150 (Pero no lo hace, selecciona cero).

2.- En cambio si la carga máxima del camión es de 500 Kilos seleccionará lo siguiente:

Paquete 9 Peso :230 valor :591
Paquete 3 Peso :153 valor :200
Paquete 4 Peso :50 valor :160
Paquete 2 Peso :9 valor :160
Paquete 1 Peso :9 valor :150

Peso total paquetes: 451
Valor total paquetes: 1261

Hace el trabajo pero no muy bien (le faltarían el 7 y el 5 para completar una carga de 493)

3.- Si la carga máxima del camión es 230 seleccionará lo siguiente:

Paquete 9 Peso :9 valor :230 

Si hace el trabajo pero mal, porque la mejor opción sería la siguiente:

Paquetes 1, 2, 4 y 5
Con un peso peso total de 83
y un valor valor total de 530 

Ya que es más eficiente.

Código:

from itertools import takewhile

#Paquetes: "Nombre del paquete", Kilos, Precio
PAQUETES = (
    ("Paquete 1", 9, 150), ("Paquete 2", 9, 160), ("Paquete 3", 153, 200), ("Paquete 4", 50, 160),
    ("Paquete 5", 15, 60), ("Paquete 6", 66, 45), ("Paquete 7", 27, 60), ("Paquete 8", 39, 40),
    ("Paquete 9", 230, 591), ("Paquete 10", 520, 10), ("Paquete 11", 110, 70), ("Paquete 12", 32, 30))

def proceso_valor(item):
    nombre, peso, valor = item
    return float(valor)

def proceso_peso(item):
    nombre, peso, valor = item
    proceso_peso.peso_maximo -= peso
    return proceso_peso.peso_maximo >= 0    

#carga máxima del camión
proceso_peso.peso_maximo = 750


carga_lista = list(takewhile(proceso_peso, reversed(sorted(PAQUETES, key=proceso_valor))))

sumacarga = 0
sumavalor = 0

for item in carga_lista:
    print item[0] + ' Peso :%i' % item[1] + ' valor :%i' % item[2]
    sumacarga = sumacarga + item[1]
    sumavalor = sumavalor + item[2]

print ''
print 'Peso total paquetes: %i' % sumacarga
print 'Valor total paquetes: %i' % sumavalor

Hay algo que no estoy viendo, necesito ayuda y las preguntas son: ¿Qué hace que mi código no funcione con valores de carga máxima pequeños (9 o 100 por ejemplo)? y ¿Qué operación matemática falta aquí para mejorar el resultado?

0

2 respuestas 2

12

Est es más simple de lo que parece: Lo que te falta es una relación precio/peso porque lo que hacés es que la función proceso_valor te devuelve solo un dato de la ecuación ¿Dónde dejas el peso?. si lo que querés es la máxima cantidad de paquetes, priorizando los de mayor valor tenes que dividir el precio por el valor para que el sorted te retorne una clave relacionada. N o se si me explico pero lo que tenes que hacer es esto:

def proceso_valor(item):
    nombre, peso, valor = item
    return float(valor)/ float(peso)

y listo, de esa forma el sorted te entregará tus 4 elementos donde el cuarto será esa relación que buscas. Si lo probás con proceso_peso.peso_maximo = 500 te entrega una carga igual a 493 y no 451 como dices con los dos paquetes que faltaban.

0
1

El problema de la mochila es un problema NP, o sea, no vas a encontrar un algoritmo que obtenga siempre la solución óptima. No obstante, lo que sí que puedes hacer es descartar los casos que peor se comporten para quedarte con las mejores soluciones posibles.

Dicho ésto, tu algoritmo debería tiene dos objetivos:

  1. Meter el mayor número de paquetes
  2. Entre las soluciones obtenidas, quedarse con los que sumen mayor valor

En tu planteamiento no queda claro si priorizar por valor es meter primero los paquetes más caros o que la suma total sea la más alta. Supongo que es éste último caso. Aunque el problema también puede ser planteado al revés: querer llevar la carga más cara, sin sobrepasar el límite de carga del camión.

Pues bien, tu algoritmo empieza por ordenar por valor y después quedarse con los que quepan en la carga máxima. Umm! Es justo lo contrario a lo que tendrías que probar. Para empezar, todos los paquetes caros los estás restando de la carga máxima. Por ejemplo, prueba con dos paquetes:

proceso_peso.peso_maximo = 750

PAQUETES = (
    ("Paquete 1", 9, 150), ("Paquete 2", 1000, 10000)
    )

carga_lista = list(takewhile(proceso_peso, reversed(sorted(PAQUETES, key=proceso_valor))))

El Paquete 2 tiene mucho valor y mucho peso. Al comprobar con proceso_peso restas su peso a proceso_peso.peso_maximo, que da negativo, y el takewhile termina devolviendo una lista vacía.

Una vez visto el fallo, mi consejo es que no uses atributos de función y, más importante, no cambies las condiciones del problema dentro de una iteracción (y si lo haces, que se vea claro). Para lo primero, usa programación orienta a objetos; para lo segundo, usa programación funcional. Para ambas cosas, usa python.


El problema de la mochila está bastante estudiado. Seguro que encuentras varios algoritmos que intentan dar con la solución de una manera más o menos rápida. Por si te sirve de pista te pongo cómo se haría por "fuerza bruta", aunque tarda muchísimo tiempo en algunos casos:

from operator import itemgetter

#Paquetes: "Nombre del paquete", Kilos, Precio
PAQUETES = (
    ("Paquete 1", 9, 150), ("Paquete 2", 9, 160), ("Paquete 3", 153, 200), ("Paquete 4", 50, 160),
    ("Paquete 5", 15, 60), ("Paquete 6", 66, 45), ("Paquete 7", 27, 60), ("Paquete 8", 39, 40),
    ("Paquete 9", 230, 591), ("Paquete 10", 520, 10), ("Paquete 11", 110, 70), ("Paquete 12", 32, 30))

#carga máxima del camión
PESOMAXIMO = 230

# Útiles para acceso al peso y valores (irían mejor definiendo una clase)
get_peso = itemgetter(1)
get_valor = itemgetter(2)

def total_peso(paquetes):
    return sum(get_peso(x) for x in paquetes)

def total_valor(paquetes):
    return sum(get_valor(x) for x in paquetes)

# Obtención de todas las combinaciones posibles
# Función recursiva
def combinaciones(paquetes, peso_maximo):
    paqs = [ p for p in paquetes if get_peso(p) <= peso_maximo ]
    resultado = []
    for p in paqs:
        res = combinaciones([x for x in paqs if x!=p], peso_maximo - get_peso(p))
        if len(res) == 0:
            resultado.append([p])
        else:
            resultado.extend([[p]+x for x in res])
    return resultado

# solución
max(combinaciones(PAQUETES, PESOMAXIMO), key=total_valor)
5
  • Está bastante buena la solución aunque me pasó que a medida que aumento la carga máxima del camión ( ´PESOMAXIMO´) aumenta demasiado el tiempo de respuesta. Sobre 800 hay que matar el proceso por que es mucha la demora. Esperemos alguna otra respuesta si no hay nada mejor me quedo con esta. Commented el 28 feb. 2016 a las 1:21
  • Creo que no entiendes bien la naturaleza del problema. A medida que aumentas el número de elementos, la complejidad aumenta de manera no-lineal. Podría ponerte una solución realizable con programación dinámica para el caso de tener 50 paquetes, pero dudo que te fuera inteligible, sobre todo sin haber intentado mejorar casos más simples. Prefiero que pruebes y, si no te sale, que hagas otra pregunta aportando hasta donde hayas logrado. Si no quieres pensar, busca por knapsack y encontrarás ejemplos, aunque sin esperar maravillas. Commented el 28 feb. 2016 a las 2:25
  • ¿No sería mejor proponer una solución pensada en programación dinámica en lugar de utilizar un algoritmo greedy como el de Eduardo o uno de fuerza bruta que puede tomar una infinidad de tiempo con un gran número de elementos? Por lo menos el algoritmo de programación dinámica puede reducirla ejecución aproximadamente a tiempo cuadrático
    – user227
    Commented el 28 feb. 2016 a las 2:30
  • @ChemaCortes : Dos preguntas solo para aclara tu comentario: 1.- ¿Qué te hace creer que no entiendo la naturaleza del problema? 2.- ¿ Que te hace creer que no quiero pensar?. Creo que una comentario como el de Luiggi Mendoza es bastante más razonable. Commented el 28 feb. 2016 a las 15:03
  • 1
    Siento que mi comentario no haya sido del todo afortunado. Lo que quiero decir que pasar de la pregunta inicial, donde se pide el porqué falla un código, a donde se pide un código que dé una solución en tiempo razonable, requiere de toda una clase magistral sobre Investigación Operacional que no creo que sea éste el sitio para tenerla. Si realizas una nueva pregunta con algún algoritmo que hayas probado para resolver el problema, estaré encantado de ayudarte. Commented el 28 feb. 2016 a las 18:09

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.