お年玉の袋をできるだけたくさん作る、という問題

質問

硬貨をたくさん集めて１０００円以上のお年玉袋をできるだけたくさん作りたい、という問題ですが、

枚数＝ａ＋ｂ＋ｃ＋ｄ＋ｅ＋ｆ（枚）
合計＝ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋５００ｆ（円）

と置くと、最大何袋できるでしょうか。

回答No.3

kmee

日本の硬貨体系で考えるなら、答えは「n≦金額÷1000<n+1 となる整数n袋」です。

1円玉ですが、 a = a' + 5a'' (0≦a'<5)と置くと
1円と5円の金額は
a+5b =a' + 5a'' + 5b
=a' + 5(a''+b)
となります。
a''+b=b'+2b '' (0≦b'<2)と置くと
5(a''+b) + 10c
= 5b' + 10b''+10c
= 5b' + 10(b''+c)
となります。

以下、繰り返していくと
金額= a' + 5b' + 10c' + 50d' + 100e' + 500f' + 1000n
(0≦a'<5,0≦b'<2, ...)
の形で、一意に表わすことができます。

この状態では、「かならず n袋作ることができます」
また、 a' + 5b' + 10c' + 50d' + 100e' + 500f' < 1000 となるため、それ以上は作れません。

この限界値は、合計金額にのみ依存します。合計枚数は関係ありません。

元の問題は「組み合わせ最適化」の一種です。
この類の問題では「この式に当てはめたら一発で解ける」ということは、ほとんどありません。

y円以上に分けるとすると n≦ 総金額÷y < n+1 となる整数nを越える数に分けることはできません。
ですが、実際にnに分ける組合せが存在するかどうかは、簡単にはわからないケースが多いでしょう。

※ 特定の条件ではあります。
例えば、このお年玉問題ですが「1000円以上」ならnに分ける組合せが存在することが、式の変形から証明できました。
ですが、「1001円以上」となったとたんに困難になります。

じっくり考えるつもりなら、組み合わせ最適化問題に、どんなアプローチがあるのか、調べてはどうでしょうか。
http://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B%E6%9C%80%E9%81%A9%E5%8C%96

補足

そう、そこが引っ掛かっていたんですよね。最初から「各硬貨が５の倍数・１０の倍数である特徴を使わないこと」と書いてもよかったのですが、このお年玉問題の答えをいただいてからの方が理解していただきやすいと思い書きませんでした。

しかし、＞簡単にはわからないケースが多いでしょう　で締められてしまってはどうしようもないですね。
この質問は一旦取り下げることにします。

回答No.2

naniwacchi

こんばんわ。
a～fに関する定義とか条件が書かれていないのがマズいのかと。
#1さんは、そのあたりを指摘されているのだと思います。

おそらく、1円玉がa枚、5円玉がb枚、…500円玉がf枚ですよね。
きちんと書かないといけませんね。

で、答えなのですが、結局のところ
(合計)÷1000円の商の値にしかならないと思うのですが・・・

補足

まあ、省いて書いてしまったのは良くなかったですね。

で、＞(合計)÷1000円の商の値　というのは自分もすぐに思いつきましたが、何だか確信が持てません。
更にこの質問は、本来の問題だとイメージがつきにくいかもしれないとのアドバイスとともにいただいたダミーの質問で、本来の問題は以下の通りです。（やや長文です。）
http://oshiete.goo.ne.jp/qa/8863088.html

単純に合計を1000（前の質問だと10000）で割るのでは精度が粗いので、今回のお年玉の問題もその方法でいいのか分かりません。それで悩んでいるのですが、いかがでしょうか。

回答No.1

kadakun

？？
何か大事な制限が抜けてるんじゃ無い？
「硬貨をたくさん集めて１０００円以上のお年玉袋をできるだけたくさん作りたい」
だけじゃ、無限としか言いようが無い。

お礼

枚数＝ａ＋ｂ＋ｃ＋ｄ＋ｅ＋ｆ（枚） 合計＝ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋５００ｆ（円）
と書きました。定数を置いたので有限です。この一文も確認していただければよいですが。

補足

回答ありがとうございます、しかしこちらも何とお返事すればいいのかわかりませんが、もしかするとNo.1様のパソコン（？）画面に最初の１行しか表示されなかったのでしょうか・・・。