在算法學習中，背包問題是一個經典的組合優化難題。今天，我們用 Python 實現貪心算法來解決它。

背包問題可以簡單描述為：給定一組物品，每個物品都有自己的重量和價值，在限定的總重量內，我們如何選擇物品，使得裝入背包的物品總價值最大。

貪心算法的核心思想是在每一步選擇中都采取當前狀態下的最優選擇，也就是局部最優解，希望以此達到全局最優。

在 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"裝入背包的最大價值為: {total_value}")

在這段代碼中，首先我們將物品按照價值重量比從高到低排序。然后，遍歷物品列表，只要當前物品的重量加上已裝入物品的總重量不超過背包容量，就將該物品裝入背包，并更新總價值和總重量。

雖然貪心算法在解決背包問題時效率較高，但要注意它并不總是能得到全局最優解，它更適用于一些特定場景，如物品可分割的情況。對于 0 - 1 背包問題（物品不可分割），貪心算法可能會得到次優解。不過，理解貪心算法解決背包問題的思路，對于深入學習算法和解決實際問題都很有幫助。

審核編輯 黃宇