2万円以上でできるだけ小さい値の組み合わせを探す

質問

ある店のレシートを２万円以上集めると特典があるという企画のためにレシートを家内が集計しています。一回の買い物は、数百円から数千円で５０枚近くあると思います。家内は凝り性で、「合計が20048円かー。もっと2万円に近づけられる組み合わせは無いだろうか？」と考えています(本当の話です)。エクセルのセルにレシートごとの値は入れてあるのですが、「2万円以上でできるだけ小さい値の組み合わせを探す」にはどうすればいいのでしょうか？素人にもわかるようにお願いいたします。

回答No.5

imogasi · ベストアンサー

レシートが５０枚あるとして、2の50という示唆があるようだが、違うのでは。組み合わせ数（Conbination)になるのでしょう。５０枚より何枚取るか決まっていない（勿論５０枚以下）訳ですし。（１）１枚で２万円を越えるものは
除外。単独で応募するより他無い。（２）最大枚数は、小さいもの順に並べたとして、最小分から足して累積して行き、例えば７枚では２万円を越えず８枚で２万円を越えるとすると、５０枚から８枚を取る組みあらせ以下の回数以下のはずです。（３）最大（２万円超を除く）の方から足して行き、２まいでは２万円を越えず、３枚で２万円を越えるなら、５０枚から３枚以上を取り出す組み合わせになるのでは。結局３枚取る＋
４枚取る＋５枚取る＋・・＋８枚取る場合の数分を加算してその和を大小順に並べて２万円に近いものから組み合わせ採用する。（４）その時ある場合に採用されたレシートは、他の場合に使えないから、組み合わせで顔をだしても、脱落させていくようになるでしょう。
こういう問題は数学の分野に出すと、こういう思考に慣れた人から回答が得られて良いと思います。

お礼

これは素人にも理解できます。
素人的にはとてもわかりやすく、
簡潔な解説ありがとうございました。
すっきり！
(絶賛)
数学に投稿した方がいいのですか。

皆様もお忙しいところ、
大変速い御回答ありがとうございました。

回答No.4

gator

私も同様な質問をしたことがあります。

非常に難しい問題のようで、頂いた解答を完全に理解することはできませんでした。
素人にもわかるような回答があると良いですね。

一応URLをご参考になさってください。

以上

参考URL：

http://oshiete1.goo.ne.jp/kotaeru.php3?q=259493

お礼

ありがとうございました。
URL見ました。
やはり難しいのかなー。

補足

ありがとうございました。
URL見ました。
やはり難しいのかなー。
(原因はわかりませんが、
お礼欄に入力できなくなってしまったので
補足欄に入力しています)

回答No.3

ARC

ちょいツッコミです。

2の50乗って、 1125899906842624回もループをまわそうと思ったら、何年かかることやら(^^;。
この手のプログラミングは、将棋やチェスと同様、力ずくでは出来ません。

プログラミング的な解法は、恐らくアルゴリズム事典などを漁れば、載っているのではないでしょうか。
(あるいは、「良い」アルゴリズムがないことが証明されているかもしれません。)
とりあえずは、並べ替えの組み合わせ方の生成順をうまく作っておいて、これまでの最良スコア(2万円以上で最低金額)を超えた段階で、それより大きくなる組み合わせをスキップする、といったアルゴリズムで、(50枚程度なら)、計算可能な数にまで減らせるのではないかと思います。

って、なんだか脇道にそれまくりですね(汗
失礼しました～

お礼

1125899906842624回計算させるのは
コンピューターでも時間がかかるのですか。
すぐできるのかと思ってました。
勉強になりました。

回答No.2

takumi38

論点とずれてしまいますが、アドバイスさせていただきます。

条件は「2万円で一口」だと思いますので、合計金額を2万円で割って、最大何口応募できるかを計算します。割り算の余りは端数の合計になります。その端数をさらに最大応募可能口数で割ると、一口あたりの端数分が出ます。端数がそれ以下であれば最大口数の応募ができることになります。端数を０に近づけても最大応募口数は変わりませんので、こういったアプローチも有効かと思います。

ただ、知的好奇心を満たすために端数０を目指すのならば、邪道かもしれませんがプログラミングをしてみるのもいいかと思います。アルゴリズムとしては、
１．レシート金額を降順に並べる
２．レシートすべての組み合わせについて合計金額を求め、2万円ちょうどならそれを表示する（２の50乗とおりの組み合わせを力ずくで調べることになります。）
３．2万円ちょうどの組み合わせを最大にさせるように最適な組み合わせを選ぶ（50枚ほどなので人間にもできるでしょう）
このくらいならJavaScriptでもできそうですので、もし興味があったら挑戦してみるのも面白いかもしれません。

No.1の方も書いているように、レシートの最小金額が数百円のオーダであるのなら、少なくない確率で端数が出ることになると思います。

長くなりまして申し訳ありません。ご参考にしていただければ幸いです。

お礼

最初のほうのアプローチは使えそうですね。
でも、今回余った分は次回に持ち越しできる
(年間を通じてやっているイベントです)ので、
2万円に満たない分は次の集計時に利用したいのです。

回答No.1

daisuke-123

回答でなくて申し訳ありませんが、どの道端数が出てしまうのではないでしょうか？

また、もれなくではなく、抽選ならの話ですが、たとえば１０万円の商品を買った人と、２万円の商品を買った人の場合、１０万円の人が優先（あたりやすく）なるらしい・・・。←あくまでもうわさです。

お礼

当たりやすくなる説、面白いです。