在算法學(xué)習(xí)中，背包問題是一個經(jīng)典的組合優(yōu)化難題。今天，我們用 Python 實現(xiàn)貪心算法來解決它。

背包問題可以簡單描述為：給定一組物品，每個物品都有自己的重量和價值，在限定的總重量內(nèi)，我們?nèi)绾芜x擇物品，使得裝入背包的物品總價值最大。

貪心算法的核心思想是在每一步選擇中都采取當(dāng)前狀態(tài)下的最優(yōu)選擇，也就是局部最優(yōu)解，希望以此達(dá)到全局最優(yōu)。

在 Python 中，我們可以這樣實現(xiàn)：

收起

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}")

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

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

審核編輯 黃宇