分支限界算法 - 0-1背包问题 - 用分支限界解 0-1 背包

分支限界算法 - 0 - 1 背包问题 - 用分支限界解 0 - 1 背包

引言

在计算机科学和运筹学领域，0 - 1 背包问题是一个经典的组合优化问题，有着广泛的实际应用，比如资源分配、货物装载等。分支限界算法是解决这类问题的一种有效策略，它通过系统地搜索问题的解空间树，结合限界函数来剪去不可能包含最优解的子树，从而减少不必要的计算，提高求解效率。本文将详细介绍如何使用分支限界算法来解决 0 - 1 背包问题。

0 - 1 背包问题概述

0 - 1 背包问题描述如下：给定一组物品，每个物品有其对应的重量 (w_i) 和价值 (v_i)，以及一个容量为 (C) 的背包。要求在不超过背包容量的前提下，选择一些物品放入背包，使得背包中物品的总价值最大。这里的“0 - 1”表示每个物品只能选择放入背包（用 1 表示）或者不放入背包（用 0 表示），不能选择部分放入。

例如，有三个物品，其重量分别为 (w = [2, 3, 4])，价值分别为 (v = [3, 4, 5])，背包容量 (C = 5)。我们需要从这三个物品中选择，使得放入背包的物品总价值最大。

分支限界算法原理

分支限界算法是一种在问题的解空间树中搜索问题解的算法。它的基本思想是：从根节点开始，按照广度优先或优先队列的方式扩展节点，同时使用限界函数来估算每个节点的子树中可能存在的最优解的上界。如果某个节点的上界小于当前已经找到的最优解，则可以剪去该节点的子树，不再进行扩展，从而减少搜索空间。

解空间树

对于 0 - 1 背包问题，解空间树是一棵二叉树。每个节点代表一个部分解，从根节点到某个节点的路径表示已经对哪些物品做出了选择（0 或 1）。左子树表示选择当前物品，右子树表示不选择当前物品。

限界函数

限界函数用于估算每个节点的子树中可能存在的最优解的上界。对于 0 - 1 背包问题，一种常用的限界函数是基于贪心策略的上界估算。具体来说，先将物品按照单位重量价值 (v_i / w_i) 从大到小排序，然后从当前节点开始，尽可能多地选择单位重量价值高的物品，直到背包容量用完或没有物品可选。这样得到的总价值就是该节点子树中可能存在的最优解的上界。

算法步骤

1. 初始化：将物品按照单位重量价值从大到小排序，创建一个优先队列（最小堆），将根节点加入队列，根节点的上界初始化为基于贪心策略估算的上界。
2. 扩展节点：从优先队列中取出上界最大的节点进行扩展。对于每个扩展的节点，分别考虑选择和不选择当前物品两种情况，生成左右子节点。
3. 计算上界：对于每个子节点，计算其对应的上界。
4. 剪枝：如果某个子节点的上界小于当前已经找到的最优解，则剪去该子节点。
5. 更新最优解：如果某个叶节点的总价值大于当前最优解，则更新最优解。
6. 重复步骤 2 - 5：直到优先队列为空。

代码实现（Python）

import heapq
class Node:
    def __init__(self, level, profit, weight, bound):
        self.level = level  # 当前节点所在的层数
        self.profit = profit  # 当前节点的总价值
        self.weight = weight  # 当前节点的总重量
        self.bound = bound  # 当前节点的上界
    def __lt__(self, other):
        return self.bound > other.bound
def bound(node, n, capacity, weights, values):
    if node.weight >= capacity:
        return 0
    profit_bound = node.profit
    j = node.level + 1
    total_weight = node.weight
    while j < n and total_weight + weights[j] <= capacity:
        total_weight += weights[j]
        profit_bound += values[j]
        j += 1
    if j < n:
        profit_bound += (capacity - total_weight) * (values[j] / weights[j])
    return profit_bound
def knapsack_branch_and_bound(capacity, weights, values):
    n = len(weights)
    # 按照单位重量价值排序
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    weights = [item[0] for item in items]
    values = [item[1] for item in items]
    root = Node(-1, 0, 0, bound(Node(-1, 0, 0, 0), n, capacity, weights, values))
    max_profit = 0
    priority_queue = []
    heapq.heappush(priority_queue, root)
    while priority_queue:
        current_node = heapq.heappop(priority_queue)
        if current_node.bound > max_profit:
            # 考虑选择当前物品
            next_level = current_node.level + 1
            left_child_weight = current_node.weight + weights[next_level]
            if left_child_weight <= capacity:
                left_child_profit = current_node.profit + values[next_level]
                left_child = Node(next_level, left_child_profit, left_child_weight, 0)
                left_child.bound = bound(left_child, n, capacity, weights, values)
                if left_child.profit > max_profit:
                    max_profit = left_child.profit
                if left_child.bound > max_profit:
                    heapq.heappush(priority_queue, left_child)
            # 考虑不选择当前物品
            right_child = Node(next_level, current_node.profit, current_node.weight, 0)
            right_child.bound = bound(right_child, n, capacity, weights, values)
            if right_child.bound > max_profit:
                heapq.heappush(priority_queue, right_child)
    return max_profit
# 测试
capacity = 5
weights = [2, 3, 4]
values = [3, 4, 5]
result = knapsack_branch_and_bound(capacity, weights, values)
print("最大价值:", result)

复杂度分析

• 时间复杂度：在最坏情况下，分支限界算法的时间复杂度仍然是指数级的 (O(2^n))，其中 (n) 是物品的数量。但在实际应用中，由于剪枝操作的存在，算法的平均时间复杂度会显著降低。
• 空间复杂度：主要用于存储优先队列中的节点，空间复杂度为 (O(2^n))。

总结

分支限界算法是解决 0 - 1 背包问题的一种有效方法，通过使用限界函数进行剪枝，减少了不必要的搜索，提高了求解效率。以下是本文内容的总结表格：
| 项目 | 详情 |
| —— | —— |
| 问题描述 | 0 - 1 背包问题是在不超过背包容量的前提下，选择物品使总价值最大，每个物品只能选或不选 |
| 算法原理 | 基于解空间树和限界函数，广度优先或优先队列扩展节点，剪去不可能含最优解的子树 |
| 步骤 | 初始化、扩展节点、计算上界、剪枝、更新最优解、重复扩展直到队列为空 |
| 复杂度 | 最坏时间复杂度 (O(2^n))，空间复杂度 (O(2^n))，实际平均复杂度因剪枝降低 |

通过合理运用分支限界算法，我们可以在一定程度上高效地解决 0 - 1 背包问题，为实际应用中的资源分配等问题提供有效的解决方案。