Python 实现【购物】

摘要：from itertools import combinationsdef find_min_k_costs(n, k, prices):unique_costs = set# 枚举所有可能的购买方案for i in range(n + 1): # 选择的商品

from itertools import combinationsdef find_min_k_costs(n, k, prices):unique_costs = set# 枚举所有可能的购买方案for i in range(n + 1): # 选择的商品数量可以从 0 到 Nfor combination in combinations(prices, i): # 选 i 个商品unique_costs.add(sum(combination)) # 计算总价格并加入集合# 对所有可能的花费去重并排序sorted_costs = sorted(unique_costs)# 输出前 K 小的花费for i in range(k):print(sorted_costs[i])# 读取输入n, k = map(int, input.split)prices = list(map(int, input.split))# 计算并输出前 K 小的购买方案花费find_min_k_costs(n, k, prices)

商品的价格数组 a 的所有子集之和即为所有可能的花费。

可以使用二进制枚举来生成所有可能的购买方案（复杂度为 O(2N)O(2^N)O(2N)，但 N≤20N \leq 20N≤20 时可行）。

去重：

由于可能存在多个不同的购买方案的总价格相同，我们可以使用**集合（set）**来去重。

排序并取前K小：

计算完所有不同的花费金额后，进行排序并取前K小的值。