Raven wants to buy all products with respective price \(p\)\(\;\in\;\)\(\mathbb{P}\), and respective discount thresholds \(s \vphantom{ s}_{n}\) so that when the sum exceeds \(s \vphantom{ s}_{n}\), she gets discount \(d \vphantom{ d}_{n}\) , \(n\)\(\;=\;\)\(1\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(N\). She considers to buy one optional item with price \(q\)\(\;\in\;\)\(\mathbb{Q}\). She has also a limit of budget \(B\). How does she make the best choice?
Yuchun asked me the question, and the confusion is how we elucidate our everyday instinct. If Raven simply minimizes the total cost \(T\), she most likely wouldn’t buy any optional item. Perhaps she should introduce a penalty function \(\varphi\), which trades the total eligible discount with \(q\) . For instance, she may set \(\varphi\)\(\;\equiv\;\)\(\surd\!\)\(q\), and minimize \(T\)\(\,+\,\)\(\surd\!\)\(q\).
Alternatively, Raven may minimize the price not discounted, and when there is a tie, she minimizes the total price. Certainly, this isn’t perfect either, because it may be absurd to see it a better bargain to buy many option items to get more discount. (But people do that all the time.) In other words, we have the assumptions:
\(\mathbb{P} \vphantom{ \mathbb{P}}_{0}\)\(,\,\)\(\mathbb{P} \vphantom{ \mathbb{P}}_{1}\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(\mathbb{P} \vphantom{ \mathbb{P}}_{N}\)\(\,\mathsf{are}\,\)\(\,\mathsf{mutually}\,\)\(\,\mathsf{exclusive}\,\)\(\,\mathsf{and}\,\)\(\,\mathsf{collectively}\,\)\(\,\mathsf{exhaustive}\,\)\(\,\mathsf{of}\,\)\(\mathbb{P}\)\(;\,\)
\(q\)\(\;\in\;\)\(\mathbb{Q}\)\(;\,\)
\(P \vphantom{ P}_{n}\)\(\;\equiv\;\)\( \displaystyle\sum\limits_{\bar{p} \;\in\; \mathbb{P} \vphantom{ \mathbb{P}}_{n}}\)\(\bar{p}\)\(,\,\)\(\;\mathtt{for}\;\)\(n\)\(\;=\;\)\(1\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(N\)\(;\,\)
\(T\)\(\;=\;\)\( \displaystyle\sum\limits^{N}_{\bar{n} \;=\; 1}\)\(P \vphantom{ P}_{\bar{n}}\)\(\,-\,\)\( \displaystyle\sum\limits_{\bar{d} \;\in\; \mathbb{D}}\)\(\bar{d}\)\(\,+\,\)\(q\)\(;\,\)
\(s \vphantom{ s}_{n}\)\(\;\leq\;\)\(P \vphantom{ P}_{n}\)\(,\,\)\(\;\mathtt{for}\;\)\(d \vphantom{ d}_{n}\)\(\;\in\;\)\(\mathbb{D}\)\(;\,\)
\(\mathbb{P} \vphantom{ \mathbb{P}}_{0}\)\(,\,\)\(\mathbb{P} \vphantom{ \mathbb{P}}_{1}\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(\mathbb{P} \vphantom{ \mathbb{P}}_{N}\)\(,\,\)\(q\)\(\;=\;\)\(\underset{\bar{\mathbb{P}} \vphantom{ \bar{\mathbb{P}}}_{0} ,\, \,\dotsc\, ,\, \bar{\mathbb{P}} \vphantom{ \bar{\mathbb{P}}}_{N} ,\, \bar{q}}{ \mathrm{argmin}}\)\(P \vphantom{ P}_{0}\)\(\left[\vphantom{\bar{\mathbb{P}} \vphantom{ \bar{\mathbb{P}}}_{0} ,\, \,\dotsc\, ,\, \bar{\mathbb{P}} \vphantom{ \bar{\mathbb{P}}}_{N}}\right.\)\(\bar{\mathbb{P}} \vphantom{ \bar{\mathbb{P}}}_{0}\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(\bar{\mathbb{P}} \vphantom{ \bar{\mathbb{P}}}_{N}\)\(\left.\vphantom{\bar{\mathbb{P}} \vphantom{ \bar{\mathbb{P}}}_{0} ,\, \,\dotsc\, ,\, \bar{\mathbb{P}} \vphantom{ \bar{\mathbb{P}}}_{N}}\right]\)\(;\,\)
\(q\)\(\;=\;\)\(\underset{\bar{q}}{ \mathrm{argmin}}\)\(T\)\(\left[\vphantom{\bar{q}}\right.\)\(\bar{q}\)\(\left.\vphantom{\bar{q}}\right]\)\(;\,\)
Taking this view, we implement a brute force approach below.
#! /usr/bin/env python3
import copy
def compare_discount(**data):
budget = data["budget"]
many_discount = data["many_discount"]
many_option = data["many_option"]
many_core = data["many_core"]
many_price = many_core + many_option
separation = len(many_discount) + 1
partition = divide_optional(separation, len(many_core), len(many_option))
if not partition:
print("Error: no combination found")
quit()
print("number of partition:", len(partition))
answer = None
total_held = sum(many_core + many_option)
original_held = sum(many_core + many_option)
for method in partition:
total = 0
total += get_total(many_price, method[0])
for head in range(1, separation):
threshold = many_discount[head - 1][0]
discount = many_discount[head - 1][1]
total_part = get_total(many_price, method[head])
if not (threshold < total_part): discount = 0
total += total_part - discount
if (budget < total): continue
original = get_total(many_price, method[0])
if (original_held > original):
original_held = original
answer = method
elif (original_held == original):
if (total_held > total):
total_held = total
answer = method
if not answer:
print("Error: no solution found")
quit()
print("group not discounted:")
for item in answer[0]:
print(many_price[item], ',', sep = '')
for head in range(len(many_discount)):
group = answer[head + 1]
if not group: continue
discount = many_discount[head][1]
print("group discounted ", discount, ":", sep = '')
for item in group: print(many_price[item], ", ", sep = '', end = '')
print('')
print("total price:", total_held)
def divide_optional(separation, number_core, number_option):
partial = divide_core(separation, number_core)
if (number_option == 0): return partial
partition = []
for option in range(number_option):
for method in partial:
for index in range(separation):
#print(number_core + option)
hold = copy.deepcopy(method)
hold[index].add(number_core + option)
partition.append(hold)
return partition
def divide_core(separation, number_core):
if (number_core == 0): return divide_empty(separation)
partial = divide_core(separation, number_core - 1)
partition = []
for method in partial:
for index in range(separation):
hold = copy.deepcopy(method)
hold[index].add(number_core - 1)
partition.append(hold)
return partition
def divide_empty(separation):
method = []
for _ in range(separation): method.append(set({}))
partition = [method]
return partition
def get_total(many_price, group):
amount = 0
for index in group: amount += many_price[index]
return amount
# # # # # # # # # # # # # # # #
many_discount = [(1000, 100), (2000, 300), (4000, 800)]
many_core = (300, 500, 1000, 1200, 1800)
many_option = (600, 800, 1000)
budget = 5000
plan = compare_discount(
budget = budget,
many_discount = many_discount,
many_option = many_option,
many_core = many_core,
)
# number of partition: 12288
# group not discounted:
# group discounted 100:
# 300, 1000,
# group discounted 800:
# 500, 1200, 1800, 600,
# total price: 4500
❧ July 26, 2021