組合せの最適化問題？分かる人、教えて下さい

質問

先日、知人との日常会話から、ある数学の問題へと発展しました。どなたか、以下の様な問題の解き方及び数式を、ど素人にも分かり易い説明をつけて、教えて頂けないでしょうか？解ける問題なのかすら、正直分わからずに質問しております。宜しくお願い致します。

----------------------------------------------------
りんご一個：250円
みかん一個：120円
メロン一個：480円
イチゴ一個：50円

上記の果物を全種類最低一個ずづ買うものとし、2000円で必ず300円のおつりが出る組合せを求めよ。
----------------------------------------------------

回答No.5

supermab · ベストアンサー

思いっきり単純に説明すると、

何か数式に当てはめて効率よく解く方法を P　とします。
一つ一つ組合せを考えるなどして解く方法を NP とします。
で、
NP＝P なのか？（効率的な方法はあるけどまだ見つかっていないだけ）
NP≠P なのか？（効率的な方法は、存在しない）
という問題は、数学的に未解決の問題です。

もし解けたら、、
クレイ研究所から１億円の懸賞金がもらえます。

お礼

ご回答、有難うございます。非常に分かり易いです！頭の中のモヤモヤがすっきりしました。つまり、この手の問題は、数学的に効率良く解く数式（数字を当てはめれば、各組合せと○通りと言う様な解答が分かるる）の存在の有無が、現時点では分かっていない種類の問題と言う事なのですね。当初、私たちは単純な数学問題だと思ったのですが、考えれば考える程、簡単に解ける数式などあるのか？と疑問に思い、こちらで質問させて頂きました。かなりすっきりしました。有難うございます。

回答No.6

naniwacchi

#3です。

ある程度は数式を使うことで問題を単純化した方が、
抜け・漏れなく考えられると思います。

＞(3) 5の倍数である項に注目していくと、さらに絞り込むことができます。
たとえば、x= 0, z= 0のときを考えます。
このとき、元の関係式は
12y + 5w = 80
となります。
5wも 80も 5の倍数ですから、12yも 5の倍数でなければなりません。
すると、0 ≦ y ≦ 6より y= 0または 5としかなりえないことがわかります。
それぞれの yに対して、最後の wが決定されます。

このことを数式で（試験の解答風に）表現すると次のようになります。
12y = 80 - 5w
12y = 5* (16 - w)

12と 5は互いに素であるから、yは 5の倍数でなければならない。
0 ≦ y ≦ 6より y= 0または 5
（以下省略）

お礼

追加のご説明、有難うございます。お陰様で、理解する事が出来ました。これ以上効率の高い数式（単純に数字を当てはめれば、各組合せと○通りと言う解答が得られる様な）は、＃5の方がご回答されている様に、数学的に未解決の問題で、今現時点では存在するのか分からないと言う事の様ですね。

回答No.4

tsuyoshi2004

まずは、１個ずつは買わなくてはいけないので・・・・
各１個で９００円
１７００円にするには残り８００円です。
ぱっと思いつくのは、イチゴを１６個でしょう。（８００／５０＝１６）
１（リンゴ１個、みかん１個、メロン１個、イチゴ１７個）
そうすれば、イチゴ何個と他の果物何個で交換できるかを考えれば答えは出ます。
リンゴ１個とイチゴ５個は交換できるので、
２（リンゴ２個、みかん１個、メロン１個、イチゴ１２個）
３（リンゴ３個、みかん１個、メロン１個、イチゴ７個）
４（リンゴ４個、みかん１個、メロン１個、イチゴ２個）
リンゴが５個だとイチゴ２５なのでこれ以上は無理）
みかん５個とイチゴが１２個も交換が出来るので、
５（リンゴ１個、みかん６個、メロン１個、イチゴ５個）
みかん１０個だとイチゴが２４個必要なので、これ以上は無理。
また、ここからリンゴとイチゴの交換も無理です。
一方でメロン１個とみかん４個の交換は可能なので、
６（リンゴ１個、みかん２個、メロン２個、イチゴ５個）
以上です。
以上、６通りになるはずです。

お礼

ご解答、有難うございます。私たちも、一つ一つ組合せを考えていけば、何となく解けそうな感じはしたのですが、もっと効率的な数式があるのではないか？と思い、色々と考えたのですが、見つからず、こちらで質問させて頂きました。ただ、＃5の方のご回答をみて、効率の良い数式の存在自体が明らかでない種類の問題だと言う事で、今はかなり納得してます。

回答No.3

naniwacchi

各々1個ずつ買った後で、800円分をどう買うかということですね。
たとえば、りんご：ｘ個、みかん：ｙ個、メロン：ｚ個、イチゴ：ｗ個とすると、
250x + 120y + 480z + 50w = 800
25x + 12y + 48z + 5w = 80

x, y, z, wはともに 0以上の整数なので、
0 ≦ x ≦ 3（りんごだけを買ったとしても最大3個までしか買えない）
0 ≦ y ≦ 6（みかんだけ～）
0 ≦ z ≦ 1（メロンだけ～）
0 ≦ w ≦ 16（イチゴだけ～）

選択肢の少ないところから、場合分けをしていけば少しは効率的に組合せが出せると思います。
(1) z= 0の場合と z= 1の場合で場合分け
(2) さらに、x= 0, 1, 2, 3で場合分け
(3) 5の倍数である項に注目していくと、さらに絞り込むことができます。

補足

ご回答、有難うございます。まさに、この様な数式を使った求め方を探していました。（3）の5の倍数である項に注目していくと、さらに絞り込めるとの事ですが、この部分、もう少し分かり易くご説明頂けますでしょうか？また、もし、この数式よりさらに効率的に組合せを求める事が出来るものがあれば、併せてご教示頂けると幸いです。

回答No.2

okormazd

2000円で必ず300円のおつりだから1700円
全種類最低一個ずづ買うから900円
残りは800円
このくらいの組み合わせなら、一番安い50円16個で800円を作れるので、以下、50円15個、14個、13個、・・・と探していけば組み合わせは求まるのではないか。
メロン一個　480円　0　　0　1　480　0　　0　　0　　0
りんご一個　250円　0　　0　0　0　　1　　250　2　500
みかん一個　120円　0　　0　1　120　0　　0　　0　　0
イチゴ一個　50円　16　800　4　200　11　550　　6　300
　　　　　　　　　16　800　6　800　12　800　　8　800

一般的な解法はわかりません。

補足

早速のご回答、有難うございます。申し訳ありません。私の質問の仕方が悪かった様です。800円分を買えば良い所までは、分かったのですが、最後の800円分の組合せの求め方で、一つ一つ組合せを考えるやり方ではなく、何か数式に当てはめて、この程度の規模であれば、全ての組合せが簡単に分かる方法はあるのでしょうか・・・。

回答No.1

Tacosan

まず, 「2000円で必ず300円のおつりが出る」ということから, 金額を合計で 1700円にすればいいということになります. そして「全種類最低一個ずづ買う」ので, とりあえず全種類 1個ずつ買ってしまいます. これで 900円使うことになるので, 残り 700円分買えばいいことになります.
これにはいろいろな方法があります.
subset sum (部分和問題) かな.

補足

早速のご回答、有難うございます。申し訳ありません。私の質問の仕方が悪かった様です。700円分を買えば良い所までは、分かったのですが、最後の700円分の組合せの求め方で、一つ一つ組合せを考えるやり方ではなく、何か数式に当てはめて、この程度の規模であれば、全ての組合せが簡単に分かる方法はあるのでしょうか？和分和問題について調べてみた所、計算複雑性理論の問題の一つと言う事ですが、名前が示す様に複雑で、中身を完全に理解出来ませんでした。ただ、何となく私の質問がこれに当てはまる様には感じました（「ナップサック問題」に近いかと）。と言う事は、この様な問題は簡単に解ける問題ではない？と言う事なのでしょうか？