整数計画問題として解けば良い
入力
求める変数
最大化したい目的関数
制約
import pulp
print(pulp.__version__)
2.2
#pulp.pulpTestAll()
def solve_level_1(total_price, coupon_posession):
"""
Parameters
==========
total_price : int
注文金額
coupon_posession : array(int)
クーポン毎の所持数
Returns
=======
coupon_use : array(int)
クーポン毎の使用数
"""
# クーポン金額
coupon_price = [500, 200, 100]
m = len(coupon_price)
problem = pulp.LpProblem(sense=pulp.LpMaximize)
# 変数
coupon_use = [pulp.LpVariable('CouponUse{0}'.format(i), cat=pulp.LpInteger, lowBound=0) for i in range(m)]
# 問題
problem += pulp.lpDot(coupon_use, coupon_price) - pulp.lpSum(coupon_use)
# 制約条件
problem += pulp.lpDot(coupon_use, coupon_price) <= total_price
problem += total_price - 1000 >= pulp.lpSum(coupon_use)
for i in range(m):
problem += coupon_posession[i] - coupon_use[i] >= 0
status = problem.solve(pulp.get_solver('PULP_CHOCO_CMD'))
print(pulp.LpStatus[status])
#print(problem)
return [coupon_use[i].value() for i in range(m)]
solve_level_1(1210, [2, 1, 3])
Optimal
[2.0, 1.0, 0.0]
# テストケース
assert solve_level_1(1000, [2, 1, 3]) == [0, 0, 0]
assert solve_level_1(1210, [0, 0, 0]) == [0, 0, 0]
assert solve_level_1(1210, [2, 1, 3]) == [2, 1, 0]
assert solve_level_1(1530, [2, 1, 3]) == [2, 1, 3]
# 枚数が一番小さい組み合わせを選択する事の確認
assert solve_level_1(1500, [3, 15, 15]) == [3, 0, 0]
Optimal Optimal Optimal Optimal Optimal
入力値の追加 or 変更
追加制約
def solve_level_2(order, coupon_posession):
"""
Parameters
==========
order : array(int)
注文 (メニュー毎の注文数を表現するベクトル)
coupon_posession : array(int)
クーポン所持数
Returns
=======
coupon_use : array(int)
クーポン毎の使用数
"""
# クーポン金額
coupon_price = [500, 200, 100, 300]
m = len(coupon_price)
# メニュー価格
menu_price = [1000, 1500, 1300, 1800, 400, 500, 600]
# Pizzaフラグ
is_pizza = [1, 1, 1, 1, 0, 0, 0]
# 支払い金額
total_price = np.dot(menu_price, order)
problem = pulp.LpProblem(sense=pulp.LpMaximize)
# 変数
coupon_use = [pulp.LpVariable('CouponUse{0}'.format(i), cat=pulp.LpInteger, lowBound=0) for i in range(m)]
# 問題
problem += pulp.lpDot(coupon_use, coupon_price) - pulp.lpSum(coupon_use)
# 制約条件
problem += pulp.lpDot(coupon_use, coupon_price) <= total_price
problem += pulp.lpSum(coupon_use) <= (total_price - 1000)
for i in range(m):
problem += coupon_posession[i] - coupon_use[i] >= 0
problem += coupon_use[0] <= 2
problem += coupon_use[1] <= 2
problem += coupon_use[2] <= 3
problem += coupon_use[3] <= 1
problem += coupon_use[3] <= np.dot(order, is_pizza)
status = problem.solve()
print(pulp.LpStatus[status])
#print(problem)
return [coupon_use[i].value() for i in range(m)]
solve_level_2([0, 0, 0, 0, 2, 1, 0], [2, 1, 1, 1])
Optimal
[2.0, 1.0, 1.0, 0.0]
# テストケース
# ジェノベーゼMx1
assert solve_level_2([1, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1]) == [0, 0, 0, 0]
# マルゲリータMx1
assert solve_level_2([0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0]) == [0, 0, 0, 0]
# ポテトフライx1, グリーンサラダx1
assert solve_level_2([0, 0, 0, 0, 2, 1, 0], [2, 1, 1, 1]) == [2, 1, 1, 0]
# マルゲリータMx1
assert solve_level_2([0, 0, 1, 0, 0, 0, 0], [2, 1, 1, 1]) == [2, 0, 0, 1]
# ジェノベーゼMx1, マルゲリータMx1
assert solve_level_2([1, 0, 1, 0, 0, 0, 0], [3, 3, 4, 2]) == [2, 2, 3, 1]
Optimal Optimal Optimal Optimal Optimal
欲しい物が満たされる時の支払い金額を最小化する
入力値の追加 or 変更
変数の追加 or 変更
最小化したい目的関数
$\text{Payout} + \sum_j \text{CouponUse}_j$
追加制約
def _solve_level_3(requirements, coupon_posession, use_setmenu=True):
"""
Parameters
==========
requirements : array(int)
欲しいメニュー (メニュー毎の注文数を表現するベクトル)
coupon_posession : array(int)
クーポン所持数
Returns
=======
coupon_use : array(int)
クーポン毎の使用数
"""
#######################################################
# 定数
#######################################################
# クーポン金額
coupon_price = [500, 200, 100, 300]
m = len(coupon_price)
# メニュー価格
menu_price = [1000, 1500, 1300, 1800, 400, 500, 600]
n = len(menu_price)
# フラグ
is_pizza = [1, 1, 1, 1, 0, 0, 0]
is_L_pizza = [0, 1, 0, 1, 0, 0, 0]
is_side = [0, 0, 0, 0, 1, 1, 1]
poteto = [0, 0, 0, 0, 1, 0, 0]
#######################################################
# 定式化
#######################################################
problem = pulp.LpProblem()
# 変数
order = [pulp.LpVariable('Order{0}'.format(j), cat=pulp.LpInteger, lowBound=0) for j in range(n)]
order_price = pulp.lpDot(order, menu_price)
coupon_use = [pulp.LpVariable('CouponUse{0}'.format(i), cat=pulp.LpInteger, lowBound=0) for i in range(m)]
piza2set_item = [0, 0, 0, 0,
pulp.LpVariable('Piza2SetUse', cat=pulp.LpInteger, lowBound=0),
0, 0]
pizaL2set_item = [0, 0, 0, 0,
pulp.LpVariable('PizaL2Set1', cat=pulp.LpInteger, lowBound=0),
pulp.LpVariable('PizaL2Set2', cat=pulp.LpInteger, lowBound=0),
pulp.LpVariable('PizaL2Set3', cat=pulp.LpInteger, lowBound=0)
]
payout = order_price - pulp.lpDot(coupon_use, coupon_price)
# 最小化問題
problem += payout - pulp.lpSum(coupon_use)
# 制約条件
problem += pulp.lpDot(coupon_use, coupon_price) <= order_price
problem += pulp.lpSum(coupon_use) <= (order_price - 1000)
for i in range(m):
problem += coupon_posession[i] - coupon_use[i] >= 0
problem += coupon_use[0] <= 2
problem += coupon_use[1] <= 2
problem += coupon_use[2] <= 3
problem += coupon_use[3] <= 1
problem += coupon_use[3] <= np.dot(order, is_pizza)
problem += pulp.lpSum(piza2set_item)*2 <= pulp.lpDot(order, is_pizza)
problem += pulp.lpSum(pizaL2set_item)*2 <= pulp.lpDot(order, is_L_pizza)
if use_setmenu:
problem += pulp.lpSum(coupon_use) == 0
else:
problem += pulp.lpSum(piza2set_item) + pulp.lpSum(pizaL2set_item) == 0
for j in range(n):
problem += order[j] + piza2set_item[j] + pizaL2set_item[j] == requirements[j]
status = problem.solve()
print(pulp.LpStatus[status])
#print(problem)
print("Order {0}".format([o.value() for o in order]))
print("Order Price {0}".format(order_price.value()))
print("Piza2 Set {0}".format(pulp.lpSum(piza2set_item).value()))
print("PizaL2 Set {0}".format(pulp.lpSum(pizaL2set_item).value()))
print("Coupon Use {0}".format(sum([coupon_use[i].value() for i in range(m)])))
print('Payout {0}'.format(payout.value()))
return payout.value(), [coupon_use[i].value() for i in range(m)]
# inputs
requirements = [1, 0, 1, 0, 1, 0, 0]
coupon_posession = [1, 0, 0, 0]
# solve
payout1, result1 = _solve_level_3(requirements, coupon_posession, use_setmenu=True)
payout2, result2 = _solve_level_3(requirements, coupon_posession, use_setmenu=False)
# クーポンを使う時と、クーポンを使わずにセットメニューを使った時で支払い金額の小さい方を採用
ret = None
if payout1 > payout2:
ret = result2
else:
ret = result1
print('-------------------')
print(f'Result: {ret}, Payout: {min(payout1, payout2)}')
assert(ret == [1, 0, 0, 0])
Optimal Order [1.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0] Order Price 2300.0 Piza2 Set 1.0 PizaL2 Set 0.0 Coupon Use 0.0 Payout 2300.0 Optimal Order [1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 0.0] Order Price 2700.0 Piza2 Set 0.0 PizaL2 Set 0.0 Coupon Use 1.0 Payout 2200.0 ------------------- Result: [1.0, 0.0, 0.0, 0.0], Payout: 2200.0
# inputs
requirements = [0, 1, 0, 1, 0, 0, 1]
coupon_posession = [1, 0, 0, 0]
# solve
payout1, result1 = _solve_level_3(requirements, coupon_posession, use_setmenu=True)
payout2, result2 = _solve_level_3(requirements, coupon_posession, use_setmenu=False)
# クーポンを使う時と、クーポンを使わずにセットメニューを使った時で支払い金額の小さい方を採用
ret = None
if payout1 > payout2:
ret = result2
else:
ret = result1
print('-------------------')
print(f'Result: {ret}, Payout: {min(payout1, payout2)}')
assert(ret == [0, 0, 0, 0])
Optimal Order [0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 0.0] Order Price 3300.0 Piza2 Set 0.0 PizaL2 Set 1.0 Coupon Use 0.0 Payout 3300.0 Optimal Order [0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 1.0] Order Price 3900.0 Piza2 Set 0.0 PizaL2 Set 0.0 Coupon Use 1.0 Payout 3400.0 ------------------- Result: [0.0, 0.0, 0.0, 0.0], Payout: 3300.0