分支限界法解决01背包问题代码

### 使用分支限界法解决0/1背包问题 #### 代码实现 以下是一个基于Python的分支限界法解决0/1背包问题的具体实现。该算法通过优先队列来维护当前最优解，并利用贪心策略计算上界。 ```python import heapq class Item: def __init__(self, weight, value): self.weight = weight self.value = value self.ratio = value / weight if weight != 0 else float('inf') class Node: def __init__(self, level, profit, bound, weight, flag=None, father=None): self.level = level self.profit = profit self.bound = bound self.weight = weight self.flag = flag self.father = father def __lt__(self, other): # 定义比较规则用于priority queue的大根堆排序 return self.bound > other.bound def calculate_bound(node, n, items, capacity): if node.weight >= capacity: return node.profit else: ub = node.profit total_weight = node.weight j = node.level + 1 while j < n and total_weight + items[j].weight <= capacity: total_weight += items[j].weight ub += items[j].value j += 1 if j < n: ub += (capacity - total_weight) * items[j].ratio return ub def knapsack_branch_and_bound(capacity, weights, values): n = len(weights) items = [] for i in range(n): items.append(Item(weights[i], values[i])) items.sort(key=lambda x: x.ratio, reverse=True) max_profit = 0 pq = [] start_node = Node(-1, 0, 0, 0) start_node.bound = calculate_bound(start_node, n, items, capacity) heapq.heappush(pq, start_node) best_node = None while pq: current_node = heapq.heappop(pq) if current_node.bound > max_profit: level = current_node.level + 1 if level == n: continue next_item = items[level] # 不选下一个物品的情况 child_not_included = Node(level, current_node.profit, 0, current_node.weight, 'left', current_node) child_not_included.bound = calculate_bound(child_not_included, n, items, capacity) if child_not_included.bound > max_profit: heapq.heappush(pq, child_not_included) # 如果选择下一个物品，则更新权重和利润 if current_node.weight + next_item.weight <= capacity: child_included = Node( level, current_node.profit + next_item.value, 0, current_node.weight + next_item.weight, 'right', current_node ) if child_included.profit > max_profit: max_profit = child_included.profit best_node = child_included child_included.bound = calculate_bound(child_included, n, items, capacity) if child_included.bound > max_profit: heapq.heappush(pq, child_included) selected_items = [] temp_node = best_node while temp_node is not None: if temp_node.flag == 'right': selected_items.append(items[temp_node.level]) temp_node = temp_node.father return max_profit, list(reversed(selected_items)) # 测试数据 weights = [2, 3, 4, 5] values = [3, 4, 5, 6] capacity = 5 max_value, included_items = knapsack_branch_and_bound(capacity, weights, values) print(f"最大价值为 {max_value}") for item in included_items: print(f"选择了 物品重量={item.weight}, 物品价值={item.value} ") ``` --- #### 关键点解析 1. **节点定义**: `Node` 类表示决策树中的每一个状态，其中包含了当前层数 (`level`)、已获得的价值 (`profit`) 和剩余容量内的可能最大价值上限 (`bound`) 的信息[^2]。 2. **边界计算**: 函数 `calculate_bound()` 计算每个子树的最大可能收益作为剪枝条件的一部分。如果某个部分树无法提供更高的潜在解决方案，则不会进一步探索它[^1]。 3. **优先队列**: 利用 Python 中的 `heapq` 实现了一个大顶堆，始终选取具有最高估计值界限的活结点扩展[^1]。 4. **贪婪准则**: 对于未处理的商品按单位重量价格降序排列有助于快速接近全局最佳解路径上的局部极优位置[^3]。 ---