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

2023-12-28 01:13:21

因上努力

个人主页:丷从心

系列专栏:回溯法

果上随缘


问题描述

  • 给定 n n n种物品和一背包,物品 i i i的重量是 w i w_{i} wi?,其价值为 v i v_{i} vi?,背包的容量为 c c c
  • 如何选择装入背包中的物品,使得装入背包中物品的总价值最大
形式化描述
  • 给定 c > 0 c > 0 c>0 w i > 0 w_{i} > 0 wi?>0 v i > 0 ( 1 ≤ i ≤ n ) v_{i} > 0 (1 \leq i \leq n) vi?>0(1in),找出一个 n n n 0 ? 1 0-1 0?1向量 ( x 1 , x 2 , ? ? , x n ) (x_{1} , x_{2} , \cdots , x_{n}) (x1?,x2?,?,xn?) x i ∈ { ? 0 , 1 ? } ( 1 ≤ i ≤ n ) x_{i} \in \set{0 , 1} (1 \leq i \leq n) xi?{0,1}(1in),使得 ∑ i = 1 n w i x i ≤ c \displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \leq c i=1n?wi?xi?c,而且 ∑ i = 1 n v i x i \displaystyle\sum\limits_{i = 1}^{n}{v_{i} x_{i}} i=1n?vi?xi?达到最大
  • 0 ? 1 0-1 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=1n?vi?xi?? ? ??i=1n?wi?xi?cxi?{0,1}(1in)?


回溯法

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

时间复杂性

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

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

文章来源:https://blog.csdn.net/from__2023_11_28/article/details/135257117
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。