Refinado de código de problema de mochila
Depuración de código de problema de mochila
Depuración de código de problema de mochila
Introducción al problema de la mochila
El problema de la mochila es un problema de optimización clásico en informática y matemáticas que implica la selección de elementos que se incluirán en una mochila para maximizar el valor de los elementos respetando las restricciones de capacidad de la mochila.
En el problema hay un conjunto de elementos, cada uno con un peso y un valor. El objetivo es seleccionar un subconjunto de estos elementos para colocarlos en una mochila con una capacidad limitada de modo que el peso total de los elementos seleccionados no supere la capacidad de la mochila y se maximice el valor total de los elementos seleccionados.
El problema de la mochila tiene importantes aplicaciones en campos como la investigación de operaciones, la informática, la ingeniería y la economía. Por ejemplo, se puede utilizar para resolver problemas de asignación de recursos en la planificación de la producción, para optimizar la gestión de inventario en la gestión de la cadena de suministro, para asignar recursos en la programación de proyectos y para optimizar las inversiones en carteras financieras.
El problema de la mochila es un problema desafiante que se sabe que es NP-completo, lo que significa que no se conoce ningún algoritmo de tiempo polinómico que lo resuelva de manera óptima para todos los casos. Sin embargo, se han desarrollado muchos algoritmos de aproximación y heurísticas eficientes para resolver el problema de forma aproximada o para encontrar buenas soluciones para casos prácticos. El problema de la mochila también tiene varias extensiones y variaciones, como el problema de la mochila múltiple, el problema de la mochila acotada y el problema de la mochila 0-1.
Código con errores
import heapq
class Node:
def init(self, level, weight, value, bound):
self.level = level
self.weight = weight
self.value = value
self.bound = bound
def lt(self, other):
return self.bound > other.bound
def knapsack(file_path, max_weight):
# Read input data from file
with open(file_path ,'r') as f :
lines = file_path.readlines()
items = []
for line in lines:
weight, value = map(int, line.strip().split())
items.append((weight, value))
def knapsack_bnb(capacity, weights, values):
n = len(weights)
heap = []
# Create the root node
root = Node(-1, 0, 0, 0)
root.bound = bound(root, weights, values, capacity, n)
heapq.heappush(heap, root)
max_value = 0
while len(heap) > 0:
node = heapq.heappop(heap)
# Check if the node is promising
if node.bound > max_value:
# Create child nodes
level = node.level + 1
# Take the item
weight = node.weight + weights[level]
value = node.value + values[level]
if weight <= capacity and value > max_value:
max_value = value
if level < n-1:
bound_value = bound(Node(level, weight, value, 0), weights, values, capacity, n)
if bound_value > max_value:
heapq.heappush(heap, Node(level, weight, value, bound_value))
# Leave the item
weight = node.weight
value = node.value
if level < n-1:
bound_value = bound(Node(level, weight, value, 0), weights, values, capacity, n)
if bound_value > max_value:
heapq.heappush(heap, Node(level, weight, value, bound_value))
return max_value
def bound(node, weights, values, capacity, n):
if node.weight >= capacity:
return 0
bound_value = node.value
j = node.level + 1
totweight = node.weight
while j < n and totweight + weights[j] <= capacity:
totweight += weights[j]
bound_value += values[j]
j += 1
if j < n:
bound_value += (capacity - totweight) * values[j] / weights[j]
return bound_value
knapsack(knapsack,16)
Errores en este código
En la clase Node, el método __init__ está mal escrito. Debe tener dos guiones bajos antes y después de "init".
En la función mochila, el método readlines() debe llamarse en el objeto de archivo f, no en la ruta del archivo ruta_archivo.
La función mochila nunca se llama en el código, por lo que no producirá ningún resultado.
La última línea del código debe llamar a la función mochila_bnb en lugar de mochila, y el primer argumento debe ser la lista de elementos elementos en lugar del nombre de función mochila.
Código corregido
import heapq
class Node:
def __init__(self, level, weight, value, bound):
self.level = level
self.weight = weight
self.value = value
self.bound = bound
def __lt__(self, other):
return self.bound > other.bound
def knapsack(file_path, max_weight):
# Read input data from file
with open(file_path ,'r') as f:
lines = f.readlines()
items = []
for line in lines:
weight, value = map(int, line.strip().split())
items.append((weight, value))
return knapsack_bnb(max_weight, [item[0] for item in items], [item[1] for item in items])
def knapsack_bnb(capacity, weights, values):
n = len(weights)
heap = []
# Create the root node
root = Node(-1, 0, 0, 0)
root.bound = bound(root, weights, values, capacity, n)
heapq.heappush(heap, root)
max_value = 0
while len(heap) > 0:
node = heapq.heappop(heap)
# Check if the node is promising
if node.bound > max_value:
# Create child nodes
level = node.level + 1
# Take the item
weight = node.weight + weights[level]
value = node.value + values[level]
if weight <= capacity and value > max_value:
max_value = value
if level < n-1:
bound_value = bound(Node(level, weight, value, 0), weights, values, capacity, n)
if bound_value > max_value:
heapq.heappush(heap, Node(level, weight, value, bound_value))
# Leave the item
weight = node.weight
value = node.value
if level < n-1:
bound_value = bound(Node(level, weight, value, 0), weights, values, capacity, n)
if bound_value > max_value:
heapq.heappush(heap, Node(level, weight, value, bound_value))
return max_value
def bound(node, weights, values, capacity, n):
if node.weight >= capacity:
return 0
bound_value = node.value
j = node.level + 1
totweight = node.weight
while j < n and totweight + weights[j] <= capacity:
totweight += weights[j]
bound_value += values[j]
j += 1
if j < n:
bound_value += (capacity - totweight) * values[j] / weights[j]
return bound_value
print(knapsack("input.txt", 16)) # replace "input.txt" with the actual input file path