【回溯】0-1背包Python实现

文章目录

• • @[toc]
  • • 问题描述
    • • 形式化描述
    • 回溯法
    • 时间复杂性
    • `Python`实现

个人主页：丷从心

系列专栏：回溯法

---

问题描述

• 给定$n$种物品和一背包，物品$i$的重量是$w_i$，其价值为$v_i$，背包的容量为$c$
• 如何选择装入背包中的物品，使得装入背包中物品的总价值最大

形式化描述

• 给定$c>0$，$w_i>0$，$v_i>0(1\le i\le n)$，找出一个$n$元$0?1$向量$(x_1,x_2,?,x_n)$， x i ∈ { ? 0 , 1 ? } ( 1 ≤ i ≤ n ) x_{i} \in \set{0 , 1} (1 \leq i \leq n) xi?∈{0,1}(1≤i≤n)，使得$\sum _{i=1}^n{w}_i{x}_i\le c$，而且$\sum _{i=1}^n{v}_i{x}_i$达到最大
• $0?1$背包问题是一个特殊的整数规划问题

max ? ∑ i = 1 n v i x i { ∑ i = 1 n w i x i ≤ c x i ∈ { ? 0 , 1 ? } ( 1 ≤ i ≤ n ) \max\displaystyle\sum\limits_{i = 1}^{n}{v_{i} x_{i}} \kern{2em} \begin{cases} \displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i} \leq c} \\ x_{i} \in \set{0 , 1} (1 \leq i \leq n) \end{cases} maxi=1∑n?vi?xi?? ? ??i=1∑n?wi?xi?≤cxi?∈{0,1}(1≤i≤n)?

---

回溯法

• $0?1$背包问题是子集选取问题，解空间可用子集树表示，解$0?1$背包问题的回溯法与解装载问题的回溯法十分相似
• 在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左儿子，当右子树中有可能包含最优解时才进入右子树搜索，否则将右子树剪去
• 设$r$是当前剩余物品价值总和，$cp$是当前价值，$bestp$是当前最优价值，当$cp+r\le bestp$时，可剪去右子树，计算右子树中解的上界的更好方法是，将剩余物品以其重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，由此得到的价值是右子树中解的上界
• 为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要按顺序考察各物品即可

---

时间复杂性

• 计算上界需要$O(n)$时间，在最坏情况下有$O(2^n)$个右儿子结点需要计算上界
• 所以解$0?1$背包问题的回溯算法所需的计算时间为$O(n{2}^n)$

---

Python实现

def backtrack_knapsack(values, weights, capacity):
    n = len(values)
    # 计算物品的单位重量价值
    unit_values = [v / w for v, w in zip(values, weights)]
    # 根据单位重量价值对物品进行降序排序
    sorted_items = sorted(range(n), key=lambda k: unit_values[k], reverse=True)

    best_solution = []
    best_value = 0

    def constraint(weight):
        # 约束函数: 检查当前解是否满足容量限制
        return weight <= capacity

    def bound(weight, value, index):
        # 限界函数: 计算当前解的价值总和加上剩余物品价值作为上界, 用于剪枝
        bound = value
        remaining_capacity = capacity - weight

        for item in range(index + 1, n):
            if remaining_capacity >= weights[sorted_items[item]]:
                remaining_capacity -= weights[sorted_items[item]]
                bound += values[sorted_items[item]]
            else:
                bound += remaining_capacity * values[sorted_items[item]] / weights[sorted_items[item]]

                break

        return bound

    def backtrack(solution, weight, value, index):
        nonlocal best_solution, best_value

        if index == n:
            # 已经遍历完所有物品
            if value > best_value:
                # 如果当前解的价值更大, 更新最优解
                best_solution = solution
                best_value = value

            return

        # 尝试选择当前物品
        weight += weights[sorted_items[index]]
        value += values[sorted_items[index]]

        if constraint(weight):
            # 如果满足约束函数, 继续探索下一个物品
            backtrack(solution + [1], weight, value, index + 1)

        # 恢复回溯之前状态
        weight -= weights[sorted_items[index]]
        value -= values[sorted_items[index]]

        # 尝试不选择当前物品
        if bound(weight, value, index) >= best_value:
            # 如果当前解的上界仍然可能更好, 继续探索下一个物品
            backtrack(solution + [0], weight, value, index + 1)

    backtrack([], 0, 0, 0)

    return best_solution, best_value


values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

best_solution, best_value = backtrack_knapsack(values, weights, capacity)

print(f'最优解: {best_solution}')
print(f'最优值: {best_value}')

最优解: [0, 1, 1]
最优值: 220

---