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?