双十一
凑单问题
一年一度的双十一又到了，在这样一个日子中，可能遇到一些问题，首先是“凑单”问题。比如说，在电商活动中，经常会有“满减”，例如，“满200，减30”，在这样的情况下，我们需要达到目标，或超过目标（因为，未达到目标，是不能进行满减的）。
很显然，如果我们买200元的物品，需要付出170元（相当于85折），而买300元的东西，需要付出270元（相当于9折）。也就是说，我们需要找到一个或多个商品组合，使其价格总和尽可能接近目标金额，且超过目标金额。
积分问题
另外一个常见的问题，是“积分兑换“问题，比如说，账号中有1000积分，可以兑换若干样东西，在这样的情况下，我们需要尽可能的接近目标，但是不能超过目标（因为，超过积分的行为是不被允许的）。
很显然，积分通常有期限，剩余的积分往往不能发挥任何作用。也就是说，我们需要找到一个或多个商品组合，使其价格总和尽可能接近目标积分，但不超过目标积分。
问题解决
解决凑单问题
解决方法：
- 假如一个商品列表
prices，目标金额target，并且定义一个变量min_excess，用于记录最小的超出金额差值，best_combination用于存储最优组合。 - 从
prices中选择每一个商品，计算商品组合的总价格，如果价格超过了target，检查是否是当前最接近的组合。总价格如果未超过target，那么继续添加其他商品。 - 最终，得到最优组合
best_combination。
from itertools import combinationsdef find_best_combination(prices, target):best_combination = Nonemin_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 - targetbest_combination = combreturn best_combination, sum(best_combination) if best_combination else 0prices = [66, 33, 24, 89, 77]
target = 200best_combination, best_price = find_best_combination(prices, target)
print(f"最优组合: {best_combination}, 总价: {best_price}")这里，我们使用了一个工具，itertools库中的combinations，该函数的作用是，生成不重复的元素组合。
# 以[1, 2, 3]为例# 此时的结果为：[(1,), (2,), (3,)]
print(list(combinations([1, 2, 3], 1)))# 此时的结果为：[(1, 2), (1, 3), (2, 3)]
print(list(combinations([1, 2, 3], 2)))# 此时的结果为：[(1, 2, 3)]
print(list(combinations([1, 2, 3], 3)))解决积分兑换
与凑单问题类似，其实只需要不超过的最接近值即可。
from itertools import combinationsdef find_best_combination(prices, target):best_combination = Nonemax_total = 0for 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_pricebest_combination = combreturn best_combination, max_totalprices = [66, 33, 24, 89, 77]
target = 200best_combination, best_price = find_best_combination(prices, target)
print(f"最优组合: {best_combination}, 总积分: {best_price}")保存多个结果
有的时候，虽然我们得到了最佳结果，但是，最佳结果并不一定是我们希望的。比如说，最佳结果中，买到的商品，可能并不是我们最满意的，因此，保存多个组合方案，可以提供多种参考。
对于凑单问题：
from itertools import combinations
import heapqdef 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 - targetheapq.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 = 5top_combinations = find_top_combinations(prices, target, top_n=top_n)
print(f"最优的{top_n}种组合及其总价：")
for i, (combination, total_price) in enumerate(top_combinations, 1):print(f"组合 {i}: {combination}, 总价: {total_price}")此时，可以看到结果显示为：
最优的5种组合及其总价：
组合 1: (66, 33, 24, 77), 总价: 200
组合 2: (66, 33, 24, 89), 总价: 212
组合 3: (33, 24, 89, 77), 总价: 223
组合 4: (66, 89, 77), 总价: 232
组合 5: (66, 24, 89, 77), 总价: 256
对于积分兑换问题：
from itertools import combinations
import heapqdef 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 = 5top_combinations = find_top_combinations(prices, target, top_n=top_n)
print(f"最优的{top_n}种组合及其总价：")
for i, (combination, total_price) in enumerate(top_combinations, 1):print(f"组合 {i}: {combination}, 总价: {total_price}")此刻可以看到结果显示为：
最优的5种组合及其总价：
组合 1: (66, 33, 24, 77), 总价: 200
组合 2: (33, 89, 77), 总价: 199
组合 3: (24, 89, 77), 总价: 190
组合 4: (66, 33, 89), 总价: 188
组合 5: (66, 24, 89), 总价: 179
