「サイゼリヤで1000円あれば最大何kcal摂れるのか」を{lpSolve}で解いてみた。

こんな話がある。

後者の2つはシンプルなナップサック問題なのでRでもできそうなので以下を参考にやってみた。

momonoki2017.blogspot.com

問題としては

メニュー $i \in N$ のカロリーを $c_i \left(> 0 \right)$ 、価格を $p_i \left(> 0 \right)$ とする。予算 $C$ の範囲でカロリーの和が最大になるメニューの組み合わせを求めよ。変数 $x = \left( x_1, x_2, ..., x_n\right)$ がメニュー $i$ が選択されているならば $x_i =1$ 、そうでなければ $x_i = 0$ であるとする。

となり定式化すると

$\displaystyle 目的関数: \sum_{i=1}^{n} c_i x_i \to 最大$

$\displaystyle 制約条件: \sum_{i=1}^{n} p_i x_i \le C(今回は1000)$

$\displaystyle x_i \in {0, 1}, \forall_i \in N$

となる。

データはGitHub - marushosummers/Saizeriya_1000yenから取得済み（./dataに保存)として以下のように読み込む。

library(RSQLite)
library(dplyr)
library(knitr)

con = RSQLite::dbConnect(SQLite(), "data/saizeriya.db", synchronous="off")
d <- RSQLite::dbGetQuery(con, "select * from menu")
RSQLite::dbDisconnect(con)

d %>% 
  head() %>% 
  knitr::kable()

id	name	category	type	price	calorie	salt
1	彩りガーデンサラダ	sidedish	salad	299	130	1.1
2	小エビのサラダ	sidedish	salad	349	115	1.3
3	やわらかチキンのサラダ	sidedish	salad	299	134	1.2
4	わかめサラダ	sidedish	salad	299	92	2.1
5	イタリアンサラダ	sidedish	salad	299	196	0.7
6	シーフードサラダ	sidedish	salad	599	229	2.4

前述のリンクを参考にlpSolve::lp()で定式化した問題を解くと以下のようになる。

ans <- lpSolve::lp(direction = "max",
                   objective.in = d$calorie,
                   const.mat = matrix(d$price, nrow = 1),
                   const.dir = "<=",
                   const.rhs = 1000,
                   all.bin = TRUE)

print(ans)
Success: the objective function is 1940

d %>% 
  dplyr::mutate(is.choiced = ans$solution) %>% 
  dplyr::filter(is.choiced == 1) %>% 
  knitr::kable()

id	name	category	type	price	calorie	salt	is.choiced
25	ポテトのグリル	sidedish	appetizer	199	366	2.0	1
73	アーリオ・オーリオ(Wサイズ)	meal	pasta	574	1120	6.4	1
101	ラージライス	sidedish	rice	219	454	0.0	1

量子アニーリング計算(Wildqat)、SMTソルバー(Z3)と結果が一致した。

予算を1000円から1500円に増やすと結果は以下のようになる。

ans <- lpSolve::lp(direction = "max",
                   objective.in = d$calorie,
                   const.mat = matrix(d$price, nrow = 1),
                   const.dir = "<=",
                   const.rhs = 1500,
                   all.bin = TRUE)

d %>% 
  dplyr::mutate(is.choiced = ans$solution) %>% 
  dplyr::filter(is.choiced == 1) %>% 
  knitr::kable()

id	name	category	type	price	calorie	salt	is.choiced
63	アーリオ・オーリオ	meal	pasta	299	560	3.2	1
67	パルマ風スパゲッティ	meal	pasta	399	700	4.2	1
73	アーリオ・オーリオ(Wサイズ)	meal	pasta	574	1120	6.4	1
101	ラージライス	sidedish	rice	219	454	0.0	1

炭水化物しかなく栄養バランスが悪すぎるのでmealとdrinkは1つにしたい。制約条件に追加するにはcategoryのダミー変数を作成し、以下のように行う。（ダミー変数の作成はrecipes::step_dummy()を使用するのが最近のトレンドかもしれないが今回はfastDummies::dummy_cols()を使用してみた。)

d <- d %>%   
  dplyr::select(id, name, category, price, calorie) %>% 
  fastDummies::dummy_cols(select_columns = "category")

d %>% 
  head() %>% 
  knitr::kable()

id	name	category	price	calorie	category_sidedish
1	彩りガーデンサラダ	sidedish	299	130	1
2	小エビのサラダ	sidedish	349	115	1
3	やわらかチキンのサラダ	sidedish	299	134	1
4	わかめサラダ	sidedish	299	92	1
5	イタリアンサラダ	sidedish	299	196	1
6	シーフードサラダ	sidedish	599	229	1

constraints <- rbind(matrix(d$price, nrow = 1),
                     matrix(d$category_sidedish, nrow = 1),
                     matrix(d$category_drink, nrow = 1),
                     matrix(d$category_meal, nrow = 1))

ans <- lp(direction = "max",
          objective.in = d$calorie,
          const.mat = constraints,
          # 合計金額 <= 1000. sidediesh 1つ以上、drink 1つ、meal 1つ 
          const.dir = c("<=", ">=", "==", "=="),
          # sidedish, drink, mealを1つは選ぶ
          const.rhs = c(1000, 1, 1, 1),
          all.bin = TRUE)

d %>% 
  dplyr::select(id, name, category, price, calorie) %>% 
  dplyr::mutate(is.choiced = ans$solution) %>% 
  dplyr::filter(is.choiced == 1) %>% 
  knitr::kable()

id	name	category	price	calorie	is.choiced
25	ポテトのグリル	sidedish	199	366	1
28	フォッカチオ	sidedish	119	214	1
31	グラスワイン	drink	100	0	1
73	アーリオ・オーリオ(Wサイズ)	meal	574	1120	1