装载问题分支限界法实现代码

装载问题是一类优化问题，其目标是在给定的一些物品中选择若干个物品，使得其总重量不超过限制且总价值最大化。下面是使用分支限界法求解装载问题的 Python 代码：

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        
def load(capacity, items):
    items.sort(key=lambda x: x.value / x.weight, reverse=True)  # 按单位价值排序
    n = len(items)
    best_value = 0  # 当前最优解
    best_items = []  # 当前最优解对应的物品列表
    
    def bound(node):
        if node.weight > capacity:
            return 0  # 超出容量，不可行
        value_bound = node.value
        weight_bound = node.weight
        j = node.level + 1
        while j < n and weight_bound + items[j].weight <= capacity:
            value_bound += items[j].value
            weight_bound += items[j].weight
            j += 1
        if j < n:
            value_bound += (capacity - weight_bound) * items[j].value / items[j].weight
        return value_bound
    
    def dfs(node):
        nonlocal best_value, best_items
        if node.level == n - 1:
            if node.value > best_value:
                best_value = node.value
                best_items = [items[i] for i in node.path]
            return
        if node.value + bound(node) <= best_value:
            return  # 剪枝
        # 不选当前物品
        dfs(Node(node.level + 1, node.weight, node.value, node.path))
        # 选当前物品
        if node.weight + items[node.level + 1].weight <= capacity:
            dfs(Node(node.level + 1, node.weight + items[node.level + 1].weight,
                      node.value + items[node.level + 1].value, node.path + [node.level + 1]))
            
    class Node:
        def __init__(self, level, weight, value, path):
            self.level = level
            self.weight = weight
            self.value = value
            self.path = path
        
    dfs(Node(-1, 0, 0, []))
    return best_value, best_items

代码中，`Item` 类表示一个物品，包含重量和价值两个属性。`load` 函数接受一个容量和一个物品列表作为输入，返回最优解的总价值和所选物品列表。函数中使用了一个 `Node` 类表示搜索树中的节点，包含当前节点的层数、当前已选物品的总重量和总价值、以及已选物品的编号列表。`bound` 函数计算当前节点的上界，即将剩余物品按单位价值从高到低排序后依次加入，直到超出容量为止，然后将剩余部分按单位价值填满。`dfs` 函数是搜索过程的核心，其首先判断当前节点是否是叶子节点，如果是，则更新最优解。否则，先进行一次剪枝，如果当前节点的上界小于等于当前最优解，则直接返回；否则，继续搜索两个子节点，分别对应选或不选当前物品。