Problemas con un algoritmo de mochila de ramificación y acotamiento.
Estoy trabajando en un ejercicio de optimización de la mochila escrito en Python. El objetivo es llenar una mochila con capacidad de peso limitada con elementos de cierto valor y peso, maximizando así el valor total de la mochila. Me encontré con un problema al establecer las variables cuando se encuentra una solución mejor.
He creado una versión simplificada del código sin ninguna restricción, que demuestra mi problema. Dado que no hay restricciones, la primera solución siempre es la mejor solución, ya que es la solución en la que se toman todos los elementos.
Hay una instrucción “if” en el código que establece las variables “max_value” y “best_taken” en caso de encontrar una solución mejor.
Sin embargo: cuando la instrucción de impresión al final del código imprime las variables “max_value” y “best_taken”, “max_value” muestra el valor correcto (la suma de los primeros índices en la lista de listas asignada a la variable “items”). El valor de “best_taken” siempre termina siendo [0,0], cuando se espera un valor de [1,1] (= tomar ambos elementos).
¿Qué estoy haciendo mal?
items = [[5,3],[4,1]]
depth = 0
class BranchBound():
def __init__(self):
self.max_value = 0
self.best_taken = []
self.local_value = 0
self.local_taken = [0] * len(items)
def branch_and_bound(self, depth):
new_depth = depth
if new_depth < len(items):
# Tomar el elemento
self.local_taken[new_depth] = 1
new_depth += 1
self.branch_and_bound(new_depth)
# No tomar el elemento
new_depth = depth
self.local_taken[new_depth] = 0
new_depth += 1
self.branch_and_bound(new_depth)
else:
self.local_value = 0
for i,j in zip(self.local_taken, items):
self.local_value += i*j[0]
if self.local_value > self.max_value:
print("ping")
self.max_value = self.local_value
self.best_taken = self.local_taken
bb = BranchBound()
bb.branch_and_bound(depth)
print(bb.max_value)
print(bb.best_taken)
davy.ai
Parece que el problema radica en el hecho de que la lista
local_taken
se pasa por referencia en lugar de ser copiada, por lo tanto, cada vez que se cambia la variablelocal_taken
, también cambia la variablebest_taken
. Es por esto quebest_taken
siempre termina siendo [0,0]. Para solucionar esto, puedes crear una copia de la listalocal_taken
antes de asignarla abest_taken
.Una forma de hacer esto es utilizando el método
copy
de la lista:Con esta modificación,
best_taken
debería mostrar ahora los valores correctos.