快捷導(dǎo)航

使用python?itertools實(shí)現(xiàn)計(jì)算雙十一滿減湊單

更新時(shí)間：2024年11月12日 09:01:35 作者：仙草哥哥

一年一度的雙十一又到了,在這樣一個(gè)日子中,可能遇到一些問題,首先是“湊單”問題,本文將使用python中的itertools庫(kù)解決這一問題,感興趣的可以了解下

雙十一

湊單問題

一年一度的雙十一又到了，在這樣一個(gè)日子中，可能遇到一些問題，首先是“湊單”問題。比如說(shuō)，在電商活動(dòng)中，經(jīng)常會(huì)有“滿減”，例如，“滿200，減30”，在這樣的情況下，我們需要達(dá)到目標(biāo)，或超過(guò)目標(biāo)（因?yàn)椋催_(dá)到目標(biāo)，是不能進(jìn)行滿減的）。

很顯然，如果我們買200元的物品，需要付出170元（相當(dāng)于85折），而買300元的東西，需要付出270元（相當(dāng)于9折）。也就是說(shuō)，我們需要找到一個(gè)或多個(gè)商品組合，使其價(jià)格總和盡可能接近目標(biāo)金額，且超過(guò)目標(biāo)金額。

積分問題

另外一個(gè)常見的問題，是“積分兌換“問題，比如說(shuō)，賬號(hào)中有1000積分，可以兌換若干樣?xùn)|西，在這樣的情況下，我們需要盡可能的接近目標(biāo)，但是不能超過(guò)目標(biāo)（因?yàn)?，超過(guò)積分的行為是不被允許的）。

很顯然，積分通常有期限，剩余的積分往往不能發(fā)揮任何作用。也就是說(shuō)，我們需要找到一個(gè)或多個(gè)商品組合，使其價(jià)格總和盡可能接近目標(biāo)積分，但不超過(guò)目標(biāo)積分。

問題解決

解決湊單問題

解決方法：

1.假如一個(gè)商品列表prices，目標(biāo)金額target，并且定義一個(gè)變量min_excess，用于記錄最小的超出金額差值，best_combination用于存儲(chǔ)最優(yōu)組合。

2.從prices中選擇每一個(gè)商品，計(jì)算商品組合的總價(jià)格，如果價(jià)格超過(guò)了target，檢查是否是當(dāng)前最接近的組合?？們r(jià)格如果未超過(guò)target，那么繼續(xù)添加其他商品。

3.最終，得到最優(yōu)組合best_combination。

from itertools import combinations
 
def find_best_combination(prices, target):
    best_combination = None
    min_excess = float("inf")
    
    for i in range(1, len(prices) + 1):
        for comb in combinations(prices, i):
            total_price = sum(comb)
            
            if total_price >= target and (total_price - target) < min_excess:
                min_excess = total_price - target
                best_combination = comb
                
    return best_combination, sum(best_combination) if best_combination else 0
 
 
prices = [66, 33, 24, 89, 77]
target = 200
 
best_combination, best_price = find_best_combination(prices, target)
print(f"最優(yōu)組合: {best_combination}, 總價(jià): {best_price}")

這里，我們使用了一個(gè)工具，itertools庫(kù)中的combinations，該函數(shù)的作用是，生成不重復(fù)的元素組合。

# 以[1, 2, 3]為例
 
# 此時(shí)的結(jié)果為：[(1,), (2,), (3,)]
print(list(combinations([1, 2, 3], 1)))
 
# 此時(shí)的結(jié)果為：[(1, 2), (1, 3), (2, 3)]
print(list(combinations([1, 2, 3], 2)))
 
# 此時(shí)的結(jié)果為：[(1, 2, 3)]
print(list(combinations([1, 2, 3], 3)))

解決積分兌換

與湊單問題類似，其實(shí)只需要不超過(guò)的最接近值即可。

from itertools import combinations
 
def find_best_combination(prices, target):
    best_combination = None
    max_total = 0
    
    for i in range(1, len(prices) + 1):
        for comb in combinations(prices, i):
            total_price = sum(comb)
            
            if total_price <= target and total_price > max_total:
                max_total = total_price
                best_combination = comb
                
    return best_combination, max_total
 
 
prices = [66, 33, 24, 89, 77]
target = 200
 
best_combination, best_price = find_best_combination(prices, target)
print(f"最優(yōu)組合: {best_combination}, 總積分: {best_price}")

保存多個(gè)結(jié)果

有的時(shí)候，雖然我們得到了最佳結(jié)果，但是，最佳結(jié)果并不一定是我們希望的。比如說(shuō)，最佳結(jié)果中，買到的商品，可能并不是我們最滿意的，因此，保存多個(gè)組合方案，可以提供多種參考。

對(duì)于湊單問題：

from itertools import combinations
import heapq
 
def find_top_combinations(prices, target, top_n=5):
    heap = []
    for i in range(1, len(prices) + 1):
        for comb in combinations(prices, i):
            total_price = sum(comb)
            if total_price >= target:
                excess = total_price - target
                heapq.heappush(heap, (-excess, total_price, comb))
                if len(heap) > top_n:
                    heapq.heappop(heap)
 
    top_combinations = sorted(heap, key=lambda x: -x[0])
    return [(comb[2], comb[1]) for comb in top_combinations]
 
prices = [66, 33, 24, 89, 77]
target = 200
top_n = 5
 
top_combinations = find_top_combinations(prices, target, top_n=top_n)
print(f"最優(yōu)的{top_n}種組合及其總價(jià)：")
for i, (combination, total_price) in enumerate(top_combinations, 1):
    print(f"組合 {i}: {combination}, 總價(jià): {total_price}")

此時(shí)，可以看到結(jié)果顯示為：

最優(yōu)的5種組合及其總價(jià)：
組合 1: (66, 33, 24, 77), 總價(jià): 200
組合 2: (66, 33, 24, 89), 總價(jià): 212
組合 3: (33, 24, 89, 77), 總價(jià): 223
組合 4: (66, 89, 77), 總價(jià): 232
組合 5: (66, 24, 89, 77), 總價(jià): 256

對(duì)于積分兌換問題：

from itertools import combinations
import heapq
 
def find_top_combinations(prices, target, top_n=5):
    top_combinations = []
 
    for i in range(1, len(prices) + 1):
        for comb in combinations(prices, i):
            total_price = sum(comb)
 
            if total_price <= target:
                if len(top_combinations) < top_n:
                    heapq.heappush(top_combinations, (total_price, comb))
                else:
                    if total_price > top_combinations[0][0]:
                        heapq.heappushpop(top_combinations, (total_price, comb))
 
    top_combinations.sort(reverse=True, key=lambda x: x[0])
    return [(comb[1], comb[0]) for comb in top_combinations]
 
prices = [66, 33, 24, 89, 77]
target = 200
top_n = 5
 
top_combinations = find_top_combinations(prices, target, top_n=top_n)
print(f"最優(yōu)的{top_n}種組合及其總價(jià)：")
for i, (combination, total_price) in enumerate(top_combinations, 1):
    print(f"組合 {i}: {combination}, 總價(jià): {total_price}")

此刻可以看到結(jié)果顯示為：

最優(yōu)的5種組合及其總價(jià)：
組合 1: (66, 33, 24, 77), 總價(jià): 200
組合 2: (33, 89, 77), 總價(jià): 199
組合 3: (24, 89, 77), 總價(jià): 190
組合 4: (66, 33, 89), 總價(jià): 188
組合 5: (66, 24, 89), 總價(jià): 179

到此這篇關(guān)于使用python itertools實(shí)現(xiàn)計(jì)算雙十一滿減湊單的文章就介紹到這了,更多相關(guān)python計(jì)算滿減湊單內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: