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

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

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

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

收起

python

# 物品列表，每個(gè)元素是一個(gè)元組，包含（重量，價(jià)值）
items = [(2, 3), (3, 4), (4, 8), (5, 8), (9, 10)]
# 背包容量
capacity = 10

# 按照價(jià)值重量比從高到低排序
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"裝入背包的最大價(jià)值為: {total_value}")

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

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

審核編輯 黃宇