複数の条件からセットをたくさん作成する方法

質問

頭の良い方、どなたか教えてください。
複数の条件からセットをできるだけたくさん作成したいです。
アルゴリズムを考えてみたのですが、どうにもわからないです。

やりたいことは以下のことです。

３種類の宝石があります。
ダイヤ、ルビー、サファイアを１個ずつで１セットとします。
それぞれの宝石を作成するのには石が必要です。
必要な石の数は以下の通りです。

ダイヤの作成
・赤い石が13個必要
・青い石が30個必要

ルビーの作成
・赤い石が20個必要
・青い石が22個必要

サファイアの作成
・赤い石が5個必要
・青い石が47個必要

３人の人が共同で宝石を作成し、できるだけ多くのセットを作成したいです。
ただし、自分の石を他の人に渡すことはできません。
宝石はみんなで共有してセットを作成することができます。

山田さん
・赤い石を289個所持
・青い石を321個所持

田中さん
・赤い石を566個所持
・青い石を291個所持

池田さん
・赤い石を123個所持
・青い石を181個所持

どのような手順で振り分けを行ったら、一番効率良く数多くのセットを作成できるでしょうか。
説明が難しくて・・・意味、伝わりますかね？(^^;

回答No.2

nag0720 · ベストアンサー

８セット作ると青い石は１個だけ余るので、
山田さんの組み合わせは、
30a+22b+47c=321　または　30a+22b+47c=320　となるはず。
この組み合わせを調べると、
30*6+22*0+47*3=321
30*4+22*7+47*1=321
30*7+22*5+47*0=320
30*0+22*6+47*4=320
の４通りのみ。

同様に、田中さんの組み合わせは、
30*5+22*0+47*3=291
30*3+22*7+47*1=291
30*6+22*5+47*0=290
の３通りのみ。

で、それぞれの個数が８を超えない組み合わせは、
30*0+22*6+47*4=320
30*5+22*0+47*3=291
となって、答が出てきます。

これはたまたまうまくいっただけで、一般化はできません。

答が一発で出るアルゴリズムはないでしょう。

エクセルで求めるなら、総当り法で全ての組み合わせを調べるしかありません。

お礼

アルゴリズムはないですか。
種類が多くなるとできないのですね。
うーん、残念です。

それでも、組合せで考えていく方法は勉強になりました。
いろいろな考え方がありますね。

ありがとうございました(^^)

回答No.3

Tacosan

一般的には「整数線形計画法」で, アルゴリズム自体はありますがおそらくさほど効率的ではありません. もちろん「一般的には」なのでこの問題に限定すればいい方法があるのかもしれませんが... ちょっとわかんないなぁ.

回答No.1

nag0720

１セット作るのに必要な青い石は99個
青い石の合計は793個なので、最大でも８セットしかできない。

８セット作る組み合わせは、

山田さん：ルビー６個、サファイヤ４個
・赤い石：20×6＋5×4＝140
・青い石：22×6＋47×4＝320

田中さん：ダイヤ５個、サファイヤ３個
・赤い石：13×5＋5×3＝80
・青い石：30×5＋47×3＝291

池田さん：ダイヤ３個、ルビー２個、サファイヤ１個
・赤い石：13×3＋20×2＋5×1＝84
・青い石：30×3＋22×2＋47×1＝181

お礼

ご回答ありがとうございます！！
これを、どのようにして導き出しましたか？
その手順を知りたいです。

たとえば、青い石を一番多く持っている人から、青い石が必要な数が多い宝石から割り振っていく、とか。

エクセルで使用したいと思っているので、アルゴリズムが必要なのです。
ぜひお教えください！！