Double Eleven
Order problem
The annual Double Eleven is here again. On such a day, you may encounter some problems, first of all, the problem of "summarizing orders". For example, in e-commerce activities, there is often a "full reduction", for example, "over 200, 30 reduction". In this case, we need to achieve the goal or exceed the goal (because, if the goal is not reached, we cannot make a full reduction).
Obviously, if we buy items worth 200 yuan, we will pay 170 yuan (equivalent to 85% off), while if we buy items worth 300 yuan, we will pay 270 yuan (equivalent to 10% off). That is, we need to find one or more product combinations so that the sum of their prices is as close to the target amount as possible and exceed the target amount.
Points Questions
Another common problem is the "point redemption" problem. For example, if there are 1,000 points in the account, you can redeemed several things. In this case, we need to be as close to the target as possible, but we cannot exceed the target (because, the behavior of exceeding the points is not allowed).
Obviously, points usually have a deadline, and the remaining points often do not play any role. That is, we need to find one or more product combinations so that the sum of their prices is as close to the target points as possible, but not exceed the target points.
Problem solving
Solve the issue of order-making
Solution:
1. If a product list price, target amount, and define a variable min_excess, to record the smallest value exceeding the amount, best_combination is used to store the optimal combination.
2. Select each item from prices, calculate the total price of the product combination, and if the price exceeds the target, check whether it is the current closest combination. If the total price does not exceed the target, continue to add other items.
3. Finally, the optimal combination best_combination is obtained.
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"Optimal combination: {best_combination}, Total price: {best_price}")Here, we use a tool, combinations in the itertools library, which function is to generate non-repetitive combinations of elements.
# Take [1, 2, 3] as an example # The result at this time is: [(1,), (2,), (3,)]print(list(combinations([1, 2, 3], 1))) # The result at this time is: [(1, 2), (1, 3), (2, 3)]print(list(combinations([1, 2, 3], 2))) # The result at this time is: [(1, 2, 3)]print(list(combinations([1, 2, 3], 3)))
Solve points redemption
Similar to the issue of order-making, it only needs to not exceed the closest value.
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"Optimal combination: {best_combination}, Total points: {best_price}")Save multiple results
Sometimes, although we get the best results, the best results are not necessarily what we hope for. For example, among the best results, the product you buy may not be the one we are most satisfied with, so saving multiple combination solutions can provide multiple references.
For the order-making problem:
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
(heap, (-excess, total_price, comb))
if len(heap) > top_n:
(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"The best{top_n}Combinations and their total price：")
for i, (combination, total_price) in enumerate(top_combinations, 1):
print(f"combination {i}: {combination}, Total price: {total_price}")At this time, you can see the result as:
The best 5 combinations and their total price:
Combination 1: (66, 33, 24, 77), Total price: 200
Combination 2: (66, 33, 24, 89), Total price: 212
Combination 3: (33, 24, 89, 77), Total price: 223
Combination 4: (66, 89, 77), Total price: 232
Combination 5: (66, 24, 89, 77), Total price: 256
Regarding points redemption questions:
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:
(top_combinations, (total_price, comb))
else:
if total_price > top_combinations[0][0]:
(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"The best{top_n}Combinations and their total price：")
for i, (combination, total_price) in enumerate(top_combinations, 1):
print(f"combination {i}: {combination}, Total price: {total_price}")You can see the results as:
The best 5 combinations and their total price:
Combination 1: (66, 33, 24, 77), Total price: 200
Combination 2: (33, 89, 77), Total price: 199
Combination 3: (24, 89, 77), Total price: 190
Combination 4: (66, 33, 89), Total price: 188
Combination 5: (66, 24, 89), Total price: 179
This is the article about using python itertools to calculate the orders for full reduction in Double Eleven. For more related content on python calculation, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!