Problema con Problema de la mochila

publicado por: Anonymous

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?

solución

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.

Respondido por: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *