質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

1回答

1013閲覧

複数の制約下において最も価値が高くなる組み合わせを求めたい。

sfs

総合スコア13

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

1クリップ

投稿2019/02/28 04:25

編集2019/02/28 04:29

前提・実現したいこと

以下の様な複数の制約下においてもっとも価値が高くなる組み合わせを求めることを Python で実現したいのですが、どのようなアルゴリズムを採用すべきか皆目見当がつきません。

レストランにおいて、いくつかの制約を抱えた上で最も満足度(S)の高いメニューの組み合わせを求めたい。 いくつかの制約とは、所持金(M)、摂取カロリー(C)、胃の容積(V)である。 Mmax = 3000(yen) Cmax = 1000(kcal) Vmax = 300(mL) リゾット M = 800(yen), C = 400(kcal), V = 100(mL), S = 30 パスタ M = 900(yen), C = 500(kcal), V = 120(mL), S = 25 サラダ M = 300(yen), C = 50(kcal), V = 50(mL), S = 10 スープ M = 500(yen), C = 150(kcal), V = 100(mL), S = 12 味噌汁 M = 500(yen), C = 100(kcal), V = 90(mL), S = 13 ハンバーグ M = 1000(yen), C = 800(kcal), V = 200(mL), S = 50

ナップサック問題の一種なのでは、とは思っているのですが検索ワードも全く見当がつかないため、今回質問させていただきました。
ご教示いただけますと幸いです。よろしくお願いいたします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

典型的な 線形計画問題 と思われます。
Python だと pulp という最適化問題を解くためのライブラリがあります。

python

1import pulp 2 3# メニュー一覧 4menus = [['リゾット', 800, 400, 100, 30], 5 ['パスタ', 900, 500, 120, 25], 6 ['サラダ', 300, 50, 50, 10], 7 ['スープ', 500, 150, 100, 12], 8 ['味噌汁', 500, 100, 90, 13], 9 ['ハンバーグ', 1000, 800, 200, 50]] 10num_menus = len(menus) 11 12# 線形計画問題を作成する。 13prob = pulp.LpProblem('Menu Selection Problem', pulp.LpMaximize) 14 15# 変数を作成する。 16x = [pulp.LpVariable('x[{}]'.format(i), 0, 10, 'Integer') 17 for i in range(num_menus)] 18 19# 目的関数を作成する。 20obj = 0 21for i in range(num_menus): 22 obj += menus[i][4] * x[i] 23prob += obj 24 25# 制約条件 26money, calorie, volume = 0, 0, 0 27for i in range(num_menus): 28 money += menus[i][1] * x[i] 29 calorie += menus[i][2] * x[i] 30 volume += menus[i][3] * x[i] 31prob += (money <= 3000) # 金額 32prob += (calorie <= 1000) # カロリー 33prob += (volume <= 300) # 胃の容量 34 35# 線形計画問題の概要を表示する。 36print(prob) 37 38# 解を求める。 39status = prob.solve() 40print('Status', pulp.LpStatus[status]) 41 42total = 0 43for i, menu in enumerate(menus): 44 cnt = int(pulp.value(x[i])) 45 print('{} ({}, {}, {}, {}): {}品'.format(*menu, cnt)) 46 total += menu[4] * cnt 47print('満足度', 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 の記事を参考にしてください。

投稿2019/02/28 05:15

編集2019/02/28 05:19
tiitoi

総合スコア21956

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

sfs

2019/02/28 05:48

ご丁寧に利用すべきモジュールや非常に参考になるサンプルコードを提示してくださり、誠にありがとうございます。 tiitoi 様のご回答を参考にコードを書いてみたいと思います。重ね重ねになりますが、この度は誠にありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問