이게 뭐야

모사에서는, 기술서나 비즈니스서를 사면 일정액까지 보조해 줄 수 있다고 합니다. (책은 스스로 소유 할 수 있습니다)
사고 싶은 책이 여러 개 있고, N회 보조의 기회가 있을 때, 어느 책을 사면 좋을까요?
조합 최적화 에서 계산해 봅시다.

사고방식

책을 사면 가치는 9할이 된다고 해서 목적함수를 「0.9×구입 금액―자부액」이라고 합니다.
또, 각 기회마다 합계 구입 금액이 보조액을 넘은 분이 자복액이 됩니다.
이 목적 함수를 최대화해 봅시다.

아래는 N=1일 때의 목적함수의 이미지입니다. 기울기는 왼쪽이 0.9이고 오른쪽이 -0.1(=0.9-1)입니다.



1권의 책은 분할할 수 없기 때문에, 구입액 후보(책의 조합)는, 이산적인 점이 됩니다.

사고 싶은 책 목록

목록을 표시합니다.

파이썬

import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
a = pd.DataFrame([
    ('吾輩は猫だろう', 981),
    ('風の三四郎', 726),
    ('夏との扉', 1024),
    ('高い城の人', 1335),
    ('天王星年代記', 865),
    ('並列都市の科学', 1171),
    ('星は無慈悲な夜の王', 914),
    ('火の島かご', 463),
    ('ロボットは我', 758),
    ('未来世紀カガワ', 1507),
    ('ケイコとアベ', 689),
    ('48億円の身代金', 1412),
    ('星々の王女様', 826),
    ('猫とゆりかもめ', 649),
    ('風と共にとまる', 1083),
    ], columns=['Title', 'Price'])
a

Title
Price




0
고배는 고양이 일 것입니다.
981


1
바람의 미시로
726


2
여름과의 문
1024년


3
높은 성의 사람
1335년


4
천왕성 연대기
865


5
병렬 도시의 과학
1171년


6
별은 무자비한 밤의 왕
914


7
불의 섬 바구니
463


8
로봇은
758


9
미래 세기 카가와
1507년


10
케이코와 아베
689


11
48억엔의 몸값
1412년


12
별들의 공주님
826


13
고양이와 유리카모메
649


14
바람과 함께 머물다
1083년

파이썬으로 계산하기

횟수를 4회, 1회당 보조액을 3000엔으로 합니다.

파이썬

N = 4 # 回数
S = 3000 # 1回当たりの補助額
m = LpProblem(sense=LpMaximize)
for i in range(N):
    a[f'Var{i}'] = addbinvars(len(a))
sums = addvars(N) # 購入額
owns = addvars(N) # 自腹額
m += 0.9*lpDot(a.Price,sum(a[f'Var{i}'] for i in range(N))) - lpSum(owns)
for i in range(N):
    m += sums[i] == lpDot(a.Price,a[f'Var{i}'])
    m += owns[i] >= sums[i] - S
for _,r in a.iterrows():
    m += lpSum(r[f'Var{i}'] for i in range(N)) <= 1 # 同じ本は1冊まで
%time m.solve()
print(LpStatus[m.status])
for i in range(N):
    a[f'Val{i}'] = a[f'Var{i}'].apply(value)
    print(a[a[f'Val{i}']>0.5].iloc[:,:2])
    print(f'{i+1} 合計 {value(sums[i])}')
>>>
Wall time: 49.8 s
Optimal
      Title  Price
9   未来世紀カガワ   1507
10   ケイコとアベ    689
12   星々の王女様    826
1 合計 3022.0
       Title  Price
1      風の三四郎    726
4     天王星年代記    865
11  48億円の身代金   1412
2 合計 3003.0
      Title  Price
5   並列都市の科学   1171
8    ロボットは我    758
14  風と共にとまる   1083
3 合計 3012.0
        Title  Price
0     吾輩は猫だろう    981
6   星は無慈悲な夜の王    914
7       火の島かご    463
13    猫とゆりかもめ    649
4 合計 3007.0

꽤 시간이 걸립니다. 모델링의 궁리의 여지가 있을지도 모릅니다.
1회만이라면, 「천왕성 연대기, 별은 무자비한 밤의 왕, 불의 섬 바구니, 로봇은 나」를 사면 정확히 3000엔입니다만, 4회 사면, 그냥 조합은 없어졌습니다.

이상