Python 算法实战：用贪心算法解决背包问题

在算法学习中，背包问题是一个经典的组合优化难题。今天，我们用 Python 实现贪心算法来解决它。

背包问题可以简单描述为：给定一组物品，每个物品都有自己的重量和价值，在限定的总重量内，我们如何选择物品，使得装入背包的物品总价值{BANNED}最佳大。

贪心算法的核心思想是在每一步选择中都采取当前状态下的{BANNED}最佳优选择，也就是局部{BANNED}最佳优解，希望以此达到全局{BANNED}最佳优。

在 Python 中，我们可以这样实现：

收起

python

# 物品列表，每个元素是一个元组，包含（重量，价值） items = [(2, 3), (3, 4), (4, 8), (5, 8), (9, 10)] # 背包容量 capacity = 10 # 按照价值重量比从高到低排序 items.sort(key=lambda x: x[1] / x[0], reverse=True) total_value = 0 total_weight = 0 for item in items: if total_weight + item[0] <= capacity: total_weight += item[0] total_value += item[1] print(f"装入背包的{BANNED}最佳大价值为: {total_value}") 

在这段代码中，首先我们将物品按照价值重量比从高到低排序。然后，遍历物品列表，只要当前物品的重量加上已装入物品的总重量不超过背包容量，就将该物品装入背包，并更新总价值和总重量。

虽然贪心算法在解决背包问题时效率较高，但要注意它并不总是能得到全局{BANNED}最佳优解，它更适用于一些特定场景，如物品可分割的情况。对于 0 - 1 背包问题（物品不可分割），贪心算法可能会得到次优解。不过，理解贪心算法解决背包问题的思路，对于深入学习算法和解决实际问题都很有帮助。