どうも、先日大学院入試に無事合格した公立はこだて未来大学（以下、弊学） B4 の Ryusuke です。
弊学では、新型コロナウイルスによる影響や国際情勢の変化による食品や日用品の価格の向上により、 9 月末に生活支援事業から「 1 万円分の食堂・購買利用券」が配布されました 👏👏👏
そこで基本暇してる僕はこの利用券の最適な使い方はなんだ？と思い調べることにしました。
今回はその過程と結論についてまとめましたので、最後まで読んでいただければ幸いです。
1 万円分の食堂・購買利用券について
この「 1 万円分の食堂・購買利用券」についての詳細をまずは紹介します。
- 学生 1 人あたり、 400 円券 × 25 枚の配布
- 400 円単位での利用が可能であり、400 円以下の品物を購入した場合であってもお釣りは出ない
- 他人に譲渡してはならない
- 混雑緩和のため、利用の際はレジに並ぶ前に準備する
これがメールで送られてきた守るべきルールです。
この中で今回考慮しなければならないルールは上の 2 つだけでよさそうです。
上記のルールから、今回の購買での最適な買い物を以下のように定めます。
400 円を超えずに、満足度が最も高くなるような買い方を調べる
ということで上記の目標を掲げて最適化な買い方を模索していきましょう！
生協の職員さんには、400 ~ 410 円 での最適解を出して欲しいとお願いされていましたが、今回は諸事情により 400 円を超えない中での最適解を模索します（職員さんには報告済み）。
ご期待に添えず申し訳ございませんでした！！！！
使用するデータについて
今回使用するデータは、「購買の最適な購入の仕方を知りたくなったのでデータが欲しい」という旨を生協事務局にお問い合わせた所、情報漏洩を決してしないことを約束に提供していただけました。
提供データは、2022 年 7 月と 2022 年 10 月 1 日 〜 10 月 12 日の弊学購買での飲食物の売り上げデータです。実データの提供は中々難しいようでデータ数が少なくなってしまったのはご容赦ください。
具体的には以下のようなデータとなっていました。（一部省力）
- 商品 ID
- 商品の販売価格
- 上記期間で売れた個数
とりあえず欲しいデータは揃っているようなのでこれらをもとに調べていきます。
満足度
皆さんも気になっていることでしょう。
今回の難しいポイントは、満足度の定義です。
聞き込み調査・売り上げ個数・売り上げ金額 など色々ありそうですね。
1 つずつ確認していきましょう。
聞き込み調査
聞き込み調査は、一人ひとりにアンケートを取るため、精度が極めて高くなるメリットがある一方で、言わずもがな労力が大変というデメリットがあります。
全員にアンケート？無理無理。
と言うことで、聞き込み調査は棄却します...
売り上げ個数・売り上げ金額
続いては、売り上げ個数・売り上げ金額です。
提供データの一つに各商品の売り上げ個数があったので、これはとても使い勝手が良さそうです。
しかし、そのまま使用すると問題もあります。
売り上げ個数のみに依存してしまうと、チロルチョコのような比較的安価な商品はたくさん売れやすく、弁当やお惣菜など比較的高価な商品はたくさん売れるとは限りません。
逆に売り上げ金額のみに依存してしまうと、比較的安価な商品だとたくさん売れてもランキングの上位には来づらいです。
ですので、これらの値をそのまま使用してしまうのは避けます。
正規化・標準化
しかし、上記のデータを使わないと満足度の定義を行いようがないので、両方とも使用してみることを考えます。
ここで、売り上げ個数と売り上げ金額は単位が異なるため、このまま使用してもおそらく金額の方の変数に重視したモデルが出来上がる恐れがあります。
そこで登場するのが正規化と標準化になります。
正規化
正規化は以下の式で表されます。
x'_i = \frac{x_i - \min(x)}{\max(x) - \min(x)} \quad (i = 1, 2, ..., n)
分子が各値から最小値を引いているので、値が最小値の時に 0 になり、最大値の時に 1 になります。
つまり、どんな値でも 0 ~ 1 の間の値に変換することができます。
しかし、正規化は外れ値がある場合などに、特徴が上手く現れないことがあるので今回は使用しません。
（今回は、理由は省略します。）
標準化
標準化は以下の式で表されます。
x'_i = \frac{x_i - \bar{x}}{\sigma} \quad (i = 1, 2, ..., n)
$\bar{x}$ は平均値、$\sigma$ は標準偏差を表しています。
標準化を行うと、平均値が 0、標準偏差が 1 になります。
どちらを使う方が良いのかと言うのは時々に寄ると思いますが（自分もよく分かっていません...）、一般的には標準化を使用する場合の方が多いと良く聞くので、今回は売り上げ個数・売り上げ金額の両方のデータに対して、それぞれ標準化をおこなっていきたいと思います。
Python で標準化を計算する場合には、scikit-learn の preprocessing ライブラリにある scale メソッドを使用すれば簡単に求まります（他にも色々あります）。
ということで、売り上げ個数・売り上げ金額の両方に対してそれぞれ標準化を行い、足して 2 で割った値を満足度と定義し、400 円を超えずに満足度を最大化する買い方を考えていきます。
標準化を行うと、平均が 0 になることから値が負になるものも存在するため、後述のナップサック問題で支障が出てきてしまいます。そこで標準化を終えた値に 50 を足して正にしています。
ナップサック問題
さて、今回の買い方を調べ上げるためのアルゴリズムとして ナップサック問題 というものが広く知られています。
ナップサック問題とは、ナップサックの中に品物を詰め込んでいき、その品物の価値を最大化するという問題 です。
ナップサック問題には、通常だと容量（ナップサックの大きさ）と、それぞれの品物の大きさと価値が与えられます。
今回の場合だと、ナップサックの容量は 400 円、品物の大きさと価値はそれぞれ、品物の値段と満足度 に相当します。
品物の値段と満足度は提供データと算出した値によって、既に求まっているので、あとはプログラムを書いて最適化な組み合わせを調べるのみです！
肝心なナップサック問題のアルゴリズムに関してですが、説明をしているととても長くなりそう & 既にたくさんのナップサック問題に関する記事が存在するので、本記事は省略します。
個人的にオススメなナップサック問題の記事と練習を紹介しておくので、興味のある方・初めて知った方などは見てみると面白いと思います。
解説記事：典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
問題:ナップサック問題（アルゴ式より）
疑似コード
ここまで説明が長くなりましたが、実際に自分が書いた疑似コードを掲載しておきます。可能ならば、 Github にリポジトリを作ったりして公開したかったのですが、データの中身は非公開のため疑似コードでご容赦ください。
満足度の定義の実装
ちょーーーーざっくりでごめんなさい。
今回は紹介しきれていませんでしたが、データの整形がかなり大変でこの数倍のコード長になってしまいました。
import pandas as pd
from sklearn import preprocessing
# csv の読み込み
df = pd.read_csv("data.csv", encoding="cp932", skiprows=1)
# データの加工
df.fillna(0, inplace=True) # 欠損値の補完（ 1 つも売れてないものが NaN になっていたので 0 で補完）
'''
その他諸々データの加工・整形 (ここが長い)
...
...
...
'''
# 満足度の算出
ss_price = preprocessing.scale(df["price"])
ss_num = preprocessing.scale(df["number_of_sales"])
df["worth"] = (ss_price + ss_num) / 2
# 満足度の高い順に並び替え
df.sort_values("worth", ascending=False, inplace=True)
ナップサック問題の実装
今回のナップサック問題で苦戦したのが、通常のナップサック問題は買った商品までは知る必要はなく、単純に最大となる価値を求められれば良いですが、今回は何を買ったかが重要になってきます。
なので、 DP（動的計画法） ではなく、再帰的にナップサック問題を実装 しています。
def knapsack(i: int, Weight: int):
""" knapsack(i, Weight) := i 番目までの商品で、選んだ金額が Weight である場合"""
if i >= len_:
return 0, []
elif Weight + money[i] > capacity:
return knapsack(i + 1, Weight)
else:
worth_1, item_list_1 = knapsack(i + 1, Weight)
worth_2, item_list_2 = knapsack(i + 1, Weight + money[i])
worth_2 += worth[i]
item_list_2.append(name[i])
if worth_1 > worth_2:
return worth_1, item_list_1
else:
return worth_2, item_list_2
def total_money(items: list) -> int:
"""買う商品の合計金額を出力する"""
return sum([int(df[df["name"] == item]["price"]) for item in items])
capacity = 400 # ナップサックの大きさ（上限金額）
len_ = df_all.shape[0] # 商品の個数
worth = df_all["worth"].to_list()
money = df_all["price"].to_list()
name = df_all["name"].to_list()
total_worth, items = knapsack(0, 0)
print(f"合計金額: {total_money(items)} 円")
print(f"満足度: {total_worth}")
print(f"---選んだ商品---")
for ind, item in enumerate(items):
print(f"{ind + 1} 品目: {item}, {int(df_all[df_all['name'] == item]['price'])} 円")
最適解
プログラムを組んだ結果、最適な買い方は以下のようになりました！！
| No. | 商品名 | 金額 |
|---|---|---|
| 1 | 明治チューインガム ガブリチュウグレープ | 32 円 |
| 2 | 有楽製菓 ブラックサンダー | 32 円 |
| 3 | 山崎 おにぎり鮭ほぐし | 108 円 |
| 4 | 山崎 おにぎりツナマヨネーズ | 108 円 |
| 5 | 大塚食品 クリスタルガイザー 700PET | 118 円 |
合計 398 円
想像以上に見事な買い方が出ました！！！！！！！！！！！！！！！！！！
炭水化物・飲料水・デザートのお菓子 と、完璧すぎませんか？？
ここまで上手く行くとは思ってなかったのでおったまげました（笑）
ネタ記事は大体結論がおもしろおかしくなるはずですが（僕もそれを期待してた。）、斜め上を行く結果となりました 👏
最適解の商品を実際に食べてみた
プログラムでは最適解と出ても実際にどうかは食べてみないとわかりません。
というわけで実際に買ってきました！！
あれ？なんか少ない...？
そうです。
なんと「鮭ほぐし」と「ブラックサンダー」が売り切れていました！！！！
やはり満足度が高いが故に売り切れていたのでしょうか！？
中でもブラックサンダーに関しては自分が目視した限りでは、お菓子の中で唯一の売り切れでした...
５品中２品が売り切れ だったのは正直とても驚きました。。。
嬉しい誤算ですね 😁
しかしこの３品のみでも、ご飯に水にデザートのお菓子とバランスが取れていたので十分楽しめました！
良い結果が得られて大満足です！！
番外編
この結果 1 つだけではつまらないので、色々制約を追加したりして遊んでみました。
その結果を実際に買ってみた感想とともにどうぞ。
飲料水のみ (結果)
| No. | 商品名 | 金額 |
|---|---|---|
| 1 | サントリー天然水 550P | 118 円 |
| 2 | コカ・コーラ 綾鷹 525P | 138 円 |
| 3 | 大塚食品 クリスタルガイザー 700PET | 118 円 |
合計 374 円
飲料水のみ （実際に買ってみた）
みんな水とお茶しか満足しないのか？😡
味変が欲しい！！！！！！
ご飯のみ (結果)
| No. | 商品名 | 金額 |
|---|---|---|
| 1 | 山崎 おにぎりサーモンわさび | 129 円 |
| 2 | 山崎 おにぎり漬けまぐろ | 129 円 |
| 3 | 山崎 おにぎりツナマヨネーズ | 108 円 |
合計 366 円
ご飯のみ （実際に買ってみた）
みんな山崎おにぎり好きすぎか？😡
お腹いっぱいになります！！！！！！
100 円以下の商品のみ (結果)
| No. | 商品名 | 金額 |
|---|---|---|
| 1 | コープ ひとくちカステラ 86g | 100 円 |
| 2 | デリア 半熟ゆでたまご | 85 円 |
| 3 | ヤガイ ペンシルカルパス | 32 円 |
| 4 | 明治チューインガム ガブリチュウグレープ | 32 円 |
| 5 | カゴメ 野菜一日これ一本 200ml | 100 円 |
| 6 | 有楽製菓 ブラックサンダー | 32 円 |
合計 381 円
100 円以下の商品のみ （実際に買ってみた）
ご飯はないものの意外とバランス良いのが面白い（笑）
みんな野菜ジュース買うってことは健康に気をつけているのでしょうか？
そしてブラックサンダーは売りk...（以下略。）
今回候補となっている商品は、諸事情により弊学購買で売れている上位 100 数件のみに絞っています。
その中に 10 円程度の最も安い商品が含まれていない場合、それらの商品を足しても金額が 400 円に満たない場合がございますが、あらかじめご了承ください。
最後に
今回は企画を思いついてから 5 日ほどで、データ提供のお問い合わせ・実装・試食・本記事の執筆を行いました。いかがでしたか？
この記事は弊学生向けにと思い、基本的な説明も所々交えながら執筆を行いました。
特に新入生の皆さんは現在「データサイエンス入門」の講義を取っている学生さんも多いと思います。そこで Python を苦戦しながら学習していると思いますが、今回のこのプログラムも全て Python で行いました。このようなことも出来るようになるのでぜひ頑張ってください！！
ちなみにナップサック問題などは僕が普段取り組んでいる競技プログラミングにおいても頻出のアルゴリズムなどでこちらに興味を持たれた方がいましたらぜひ僕の Twitter までお越しください！DM 等お待ちしております。
この記事を読んで少しでも楽しんでもらえたら幸いです。
最後までありがとうございました👋