I am working with a case of a client in which he applies to use the Knapsack Problem algorithm . I am using the attached code, it works more or less and it has bugs.
The example has 12 packages of different weights (which in total weigh 1260 Kilos) with an associated value or price. The goal is to load the maximum number of packages, prioritizing the highest value without exceeding the maximum load of the truck.
For example;
1.- If the maximum load of the truck is 9 Kilos, this code should select Paquete 2 Peso :9 valor :160
and not Paquete 2 Peso :9 valor :150
(But it does not, it selects zero).
2.- On the other hand, if the maximum load of the truck is 500 Kilos, select the following:
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
Does the job but not very well (would be short of 7 and 5 to complete a 493 charge)
3.- If the maximum load of the truck is 230, select the following:
Paquete 9 Peso :9 valor :230
If it does the job but badly, because the best option would be the following:
Paquetes 1, 2, 4 y 5
Con un peso peso total de 83
y un valor valor total de 530
Since it is more efficient.
Code :
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
There is something that I am not seeing, I need help and the questions are: What makes my code not work with small maximum load values (9 or 100 for example)? and what mathematical operation is missing here to improve the result?
This is simpler than it seems: What you are missing is a price/weight relationship because what you do is that the process_value function returns only one data from the equation Where do you leave the weight?. If what you want is the maximum number of packages, prioritizing the ones with the highest value, you have to divide the price by the value so that the sorted returns a related key. I don't know if I'm explaining myself but what you have to do is this:
and ready, that way the sorted will give you your 4 elements where the fourth will be that relationship you are looking for. If you try it with process_weight.weight_maximum = 500, it gives you a load equal to 493 and not 451 as you say with the two missing packages.
The knapsack problem is an NP problem, that is, you will not find an algorithm that always obtains the optimal solution. However, what you can do is discard the worst-behaving cases to keep the best possible solutions.
That said, your algorithm should have two goals:
In your approach it is not clear if prioritizing by value is putting the most expensive packages first or that the total sum is the highest. I guess it's the latter case. Although the problem can also be put the other way around: wanting to carry the most expensive load, without exceeding the load limit of the truck.
Well, your algorithm starts by sorting by value and then keeping the ones that fit in the maximum load. umm! It's just the opposite of what you should try. To begin with, all the expensive packages you are subtracting from the maximum load. For example, try two packages:
Package 2 has a lot of value and a lot of weight. Checking with
proceso_peso
subtracts its weight fromproceso_peso.peso_maximo
, which is negative, andtakewhile
ends up returning an empty list.Having seen the bug, my advice is don't use function attributes and, more importantly, don't change the problem conditions within an iteration (and if you do, make it look clear). For the former, use object-oriented programming; for the latter, use functional programming. For both, use python.
The knapsack problem is well studied. Surely you will find several algorithms that try to find the solution more or less quickly. In case it helps you, I'll show you how it would be done by "brute force" , although it takes a long time in some cases: