貪心算法

1. 什么是貪心算法

　　貪心算法，又稱貪婪算法，是一種在解決問題的過程中追求局部最優(yōu)的算法，對(duì)于一個(gè)有多種屬性的事物來說，貪心算法會(huì)優(yōu)先滿足某種條件，追求局部最優(yōu)的同時(shí)希望達(dá)到整體最優(yōu)的效果。它并不保證得到整體的最優(yōu)解，但在某些問題上，貪心算法的解就是最優(yōu)解。

2. 找零問題

　　描述：有若干面值的紙幣，給定一個(gè)總數(shù)額，來找出最少的紙幣數(shù)量。

　　思路：利用貪心算法，先從最大的紙幣開始找，以此類推，直到找完為止

money = [100, 50, 20, 10, 5, 1]

def greedy(money, n):
    m = [0 for i in range(len(money))]
    for index, val in enumerate(money):
        m[index] = n // val
        n = n % val
    return m

3. 背包問題：背包問題分為0-1背包和分?jǐn)?shù)，分?jǐn)?shù)背包可以利用貪婪算法求

　　描述：有幾種物品，物品擁有重量和價(jià)值兩個(gè)屬性，用一個(gè)指定容量的背包去裝這些物品，物品放入包中時(shí)，物品可以不完全放入包中，而放入一部分，求價(jià)值最大的方案。

　　思路：在選擇物品i裝入背包時(shí)，可以選擇物品的一部分，而不一定要全部裝入背包。計(jì)算每種物品的單位重量價(jià)值作為貪心選擇的依據(jù)指標(biāo)，選擇單位重量價(jià)值最高的物品，將盡可能多的該物品裝入背包，依此策略一直地進(jìn)行下去，直到背包裝滿為止。在零一背包問題中貪心選擇之所以不能得到最優(yōu)解原因是貪心選擇無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。

# 分?jǐn)?shù)背包問題
goods = [(60, 10), (120, 30), (100, 20)]
# 按照價(jià)值的權(quán)重進(jìn)行排序，即價(jià)值除以重量，reverse為True表示倒序
goods.sort(key=lambda x: x[0]/x[1], reverse=True)
print(goods)
def grade_backage(goods, w):
    m = [0 for i in range(len(goods))]
    total_p = 0
    for i, (prize, weight) in enumerate(goods):
        if w >= weight:
            m[i] = 1
            total_p += prize
            w -= weight
        else:
            m[i] = w / weight
            total_p += m[i] * prize
            break
    return total_p, m

print(grade_backage(goods,40))

posted @ 2023-01-13 23:35 無敵小豆包閱讀(332) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部

貪心算法

公告