Python中的背包问题

2025年1月5日 | 阅读6分钟

在本教程中，我们将学习如何用 Python 解决背包问题。我们将使用几种方法来找到解决方案。在这个问题中，我们有一组 N 件物品，每件物品都有其重量和价值。我们的目标是以一种最大化背包中物品总价值的方式，选择物品并将它们放入一个容量有限的背包中，该容量表示为 W。需要强调的是，我们只能选择每件物品一次。

换句话说，我们提供了两个数组：一个包含价值 (val)，另一个包含 N 件物品的重量 (wt)。此外，还有一个整数 W，表示背包的最大承重。我们的任务是确定 val 数组中最有价值的物品组合，同时确保 wt 数组中对应重量的总和不超过背包的容量。请注意，您不能分割物品；您可以将其完全放入您的选择中，或者将其丢弃。这个问题通常被称为 0/1 背包问题。

示例 1

输入

N = 4
W = 6
Values[] = {5,7,2,4}
Weights[] = {3,4,5,2}

输出

解释：为了在背包容量为 6 的情况下最大化价值，请选择第一件价值为 5 的物品和第四件价值为 4 的物品。

示例 2

输入

N = 5
W = 7
Values[] = [3,8,6,2,5]
Weights[] = [2,3,4,7,1]

输出

解释：选择第二件和第五件物品，在背包容量允许的情况下获得最大的总价值 12。

让我们用各种方法来解决上述问题。

方法 1：蛮力法

首先，我们将使用蛮力法来解决这个问题。使用此方法解决 0/1 背包问题涉及生成所有可能的物品组合，并计算每种组合的总价值。然后，我们选择不超出背包容量且具有最大价值的组合。以下是此蛮力法的 Python 实现。

示例 -

def knapsack_bruteforce(values, weights, capacity):
    n = len(values)
    
    # Function to calculate the total value of a combination
    def get_total_value(combination):
        total_value = 0
        total_weight = 0
        for i in range(n):
            if combination[i] == 1:
                total_value += values[i]
                total_weight += weights[i]
        return total_value, total_weight
    
    # Initialize variables to keep track of the best combination and its value
    best_combination = [0] * n
    best_value = 0
    
    # Generate all possible combinations using binary representation
    for i in range(2**n):
        combination = [int(bit) for bit in bin(i)[2:].zfill(n)]
        total_value, total_weight = get_total_value(combination)
        
        # Check if this combination is feasible and has a higher value
        if total_weight <= capacity and total_value > best_value:
            best_combination = combination
            best_value = total_value
    
    return best_value, best_combination

# Example usage
values = [1, 2, 3]
weights = [4, 5, 1]
capacity = 4
max_value, best_combination = knapsack_bruteforce(values, weights, capacity)
print("Maximum Value:", max_value)
print("Selected Items:", best_combination)

输出

Maximum Value: 3
Selected Items: [0, 0, 1]

解释 -

让我们来理解代码的以下步骤。

首先，我们定义一个名为 knapsack_bruteforce() 的函数，该函数接受三个参数：values、weights 和 capacity。这些参数分别表示物品的价值、重量和背包的容量。
在函数内部，它计算 `values` 列表的长度（物品数量）并将其分配给变量 n。
然后我们在主函数内定义 get_total_value() 函数。此内部函数计算由二进制列表表示的物品组合的总价值和总重量。
它初始化变量 best_combination（一个零列表，表示未选择任何物品）和 best_value（初始化为 0），以跟踪迄今为止找到的最佳组合。
然后它进入一个循环，该循环生成所有可能的物品组合。它使用从 0 到 2^n（n 是物品数量）的数字的二进制表示来指示物品选择。
对于每种组合，它会调用 get_total_value() 函数来计算该组合的总价值和总重量。
它检查组合是否可行（总重量不超过背包容量）以及它是否比迄今为止找到的最佳组合具有更高的总价值。
如果满足这些条件，它会更新 best_combination 和 best_value 以及当前组合及其总价值。
在检查完所有可能的组合后，该函数返回最大总价值（`best_value`）和相应的选定物品组合（`best_combination`）。

请记住，由于其指数级时间复杂度，蛮力法对于背包问题的较大实例效率低下。为了克服这一点，我们将使用动态规划进行高效的解决方案。

方法 2：动态规划法

让我们理解以下示例 -

示例 -

def knapsack_max_value(capacity, weights, values):
    n = len(values)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for w in range(capacity + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif weights[i - 1] <= w:
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]
# Example usage
values = [1, 2, 3]
weights = [4, 5, 1]
capacity = 4
max_value = knapsack_max_value(capacity, weights, values)
print("Maximum Value:", max_value)

输出

Maximum Value: 3

解释 -

让我们来理解使用动态规划的 0/1 背包问题的以下代码。

定义了 knapsack_max_value() 函数来查找在给定背包容量内可以获得的最大价值，它接受三个参数 - 第一个参数 capacity 代表背包的最大承重。第二个参数 weight 是一个代表物品重量的列表，values 是一个代表物品价值的列表。
变量 n 初始化为 values 列表的长度，表示物品的数量。
创建一个二维列表 dp 来存储不同物品组合和容量实现的最高价值。它有 (n + 1) 行和 (capacity + 1) 列。
动态规划算法以自下而上的方式构建 dp 表，考虑所有可能的物品组合和容量。
两个嵌套循环遍历物品数量 (i) 和可用容量 (w)。对于每种组合
1. 如果剩余的物品数量为零 (`i == 0`) 或背包的容量为零 (`w == 0`)，则最大值为 0。
2. 如果当前物品的重量 (`weights[i-1]`) 小于或等于可用容量 (`w`)，则算法通过考虑两个选项来计算最大值：包含当前物品和不包含当前物品。
3. 如果当前物品的重量大于可用容量，则最大值与不包含此物品所获得的最大值相同。
该函数返回动态规划过程结束时获得的最大值，该值存储在 `dp[n][capacity]` 中。
在示例用法中，代码演示了如何使用一组示例值、重量和背包容量来使用 knapsack_max_value() 函数。它会打印出在给定约束条件下可以达到的最大值。

动态规划方法通过考虑所有可能的组合并选择在满足背包容量要求的情况下价值最大的组合，从而有效地解决了 0/1 背包问题。

方法 3：贪心算法

贪心算法是一种用于解决优化问题的技术，其目标是根据一组特定标准发现最佳解决方案。这些算法在每一步都做出看似最有利的决策，期望这些局部最优选择最终能带来最有利的整体解决方案。

示例 -

def knapsack_greedy(values, weights, capacity):
    n = len(values)
    value_per_weight = [(values[i] / weights[i], values[i], weights[i]) for i in range(n)]
    # Sort items by value-to-weight ratio in descending order
    value_per_weight.sort(reverse=True)

    total_value = 0
    selected_items = [0] * n

    for i in range(n):
        if capacity == 0:
            break
        if value_per_weight[i][2] <= capacity:
            total_value += value_per_weight[i][1]
            capacity -= value_per_weight[i][2]
            selected_items[i] = 1

    return total_value, selected_items
values = [1, 2, 3]
weights = [4, 5, 1]
capacity = 4
max_value, best_combination = knapsack_greedy(values, weights, capacity)
print("Maximum Value (Greedy Approach):", max_value)
print("Selected Items:", best_combination)

输出

Maximum Value (Greedy Approach): 3
Selected Items: [1, 0, 0]

结论

在本教程中，我们探讨了在 Python 中解决 0/1 背包问题的各种方法。我们讨论了蛮力法，该方法系统地生成所有可能的物品组合；动态规划法，该方法使用二维表高效地计算最优解；以及贪心算法，该算法基于价值-重量比做出局部最优选择。

动态规划法是最有效的，而贪心算法则提供了一种快速但不总是最优的解决方案。方法选择取决于问题的大小以及对最优解或启发式解决方案的需求。

下一个主题不使用额外空间的合并两个排序数组

Python中的背包问题

示例 1

示例 2

方法 1：蛮力法

方法 2：动态规划法

方法 3：贪心算法

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

其他

Python中的背包问题

示例 1

示例 2

方法 1：蛮力法

方法 2：动态规划法

方法 3：贪心算法

结论

相关帖子

将字节写入Python文件

Python中的Wand vignette()函数

Python中的随机游走实现

2024年开发者必备的10个Python CLI库

使用Python .docx模块处理图像

Python中的Minimax算法

Python 身份运算符

Python中的Matplotlib.pyplot.annotate()

使用Python进行投资组合优化

Python中的数据科学

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器