質問: 50 ``` ナップサック問題の一種なのでは、とは思っているのですが検索ワードも全く見当がつかないため、今回質問させていただきました。 ご教示いただけますと幸いです。よろしくお願いいたします。
回答: 典型的な 線形計画問題 と思われます。 Python だと pulp という最適化問題を解くためのライブラリがあります。 ``` import pulp # メニュー一覧 menus = [['リゾット', 800, 400, 100, 30], ['パスタ', 900, 500, 120, 25], ['サラダ', 300, 50, 50, 10], ['スープ', 500, 150, 100, 12], ['味噌汁', 500, 100, 90, 13], ['ハンバーグ', 1000, 800, 200, 50]] num_menus = len(menus) # 線形計画問題を作成する。 prob = pulp.LpProblem('Menu Selection Problem', pulp.LpMaximize) # 変数を作成する。 x = [pulp.LpVariable('x[{}]'.format(i), 0, 10, 'Integer') for i in range(num_menus)] # 目的関数を作成する。 obj = 0 for i in range(num_menus): obj += menus[i][4] * x[i] prob += obj # 制約条件 money, calorie, volume = 0, 0, 0 for i in range(num_menus): money += menus[i][1] * x[i] calorie += menus[i][2] * x[i] volume += menus[i][3] * x[i] prob += (money <= 3000) # 金額 prob += (calorie <= 1000) # カロリー prob += (volume <= 300) # 胃の容量 # 線形計画問題の概要を表示する。 print(prob) # 解を求める。 status = prob.solve() print('Status', pulp.LpStatus[status]) total = 0 for i, menu in enumerate(menus): cnt = int(pulp.value(x[i])) print('{} ({}, {}, {}, {}): {}品'.format(*menu, cnt)) total += menu[4] * cnt print('満足度', total) ``` 定式化 ``` 目的関数 (最大化) # 満足度を最大化 30*x_0_ + 25*x_1_ + 10*x_2_ + 12*x_3_ + 13*x_4_ + 50*x_5_ + 0 制約条件 # 費用の合計は3000円以下 _C1: 800 x_0_ + 900 x_1_ + 300 x_2_ + 500 x_3_ + 500 x_4_ + 1000 x_5_ <= 3000 # カロリーの合計は1000以下 _C2: 400 x_0_ + 500 x_1_ + 50 x_2_ + 150 x_3_ + 100 x_4_ + 800 x_5_ <= 1000 # 胃の容量の合計は300以下 _C3: 100 x_0_ + 120 x_1_ + 50 x_2_ + 100 x_3_ + 90 x_4_ + 200 x_5_ <= 300 変数 (0 ~ 10個注文できる) 0 <= x_0_ <= 10 Integer 0 <= x_1_ <= 10 Integer 0 <= x_2_ <= 10 Integer 0 <= x_3_ <= 10 Integer 0 <= x_4_ <= 10 Integer 0 <= x_5_ <= 10 Integer ``` 答え ``` Status Optimal リゾット (800, 400, 100, 30): 2品 サラダ (300, 50, 50, 10): 2品 満足度 80 ``` 使い方は公式ドキュメントや Qiita の記事を参考にしてください。 * PuLP による線型計画問題の解き方ことはじめ * Python+PuLPによるタダで仕事に使える数理最適化 * 数理最適化モデラー(PuLP)チートシート(Python) * pythonのPuLPを用いて線形計画問題を解いてみる