箱詰め                                    戻る

 当HPがいつもお世話になっているHN「GAI」さんからの出題です。
                                        (平成27年4月9日付け)

 重さ(g)が、

 442,252,252,252,252,252,252,252,127,127,127,127,127,106,106,106,106,85,84,46,37,37,12,12,12,
 10,10,10,10,10,10,9,9

である33個の荷物があり、これらを524(g)までを郵送可能な箱に詰めて送りたい。

 郵送料金をおさえるためには何箱にどの様に詰め込めばよいか?


































(答え) らすかるさんが考察されました。(平成27年4月9日付け)

 (重さの合計)=3668g=524g×7 だから、最少7箱

 442+46+12×3=524 、252×2+10×2=524 、252×2+10×2=524 、252×2+10×2=524
 252+127×2+9+9=524 、127×3+106+37=524 、106×3+85+84+37=524

で、丁度おさまりました。


 GAI さんからの追加問題です。(平成27年4月10日付け)

 冒頭の問題に対して、らすかるさんが見事に理想の箱詰めを見つけられました。ところが、
完成した途端、箱詰めの中の46(g)のものがのどうしても必要になり、同じ箱だったので全て
の箱を空け、その46(g)を取り除き、新たに

 442,252,252,252,252,252,252,252,127,127,127,127,127,106,106,106,106,85,84,37,37,12,12,12,
 10,10,10,10,10,10,9,9

の32個のものをもう一度箱詰めすることになった。

 生憎、メモを取っていなかったので前の箱詰め方法がわからなくなり、改めて考え直すこと
になった。(ここは別の箱詰め方法と解釈して下さい。)

 さてあなたは、どの様な箱詰めをしますか?


 らすかるさんからのコメントです。(平成27年4月10日付け)

 (重さの合計)=3622g=524g×7-46gだから、最少7箱で、7箱のとき524gとなる不足分の合計
が46gとなる。

 前問と同じように、重いものを優先として、なるべく524gに近くなるように詰めていくと、

 442+37+12×3+9=524 、252×2+10×2=524 、252×2+10×2=524 、252×2+10×2=524
 252+127+106+37=522 (524gに2g足らず) 、127×4+9=517 (524gに7g足らず)
 106×3+85+84=487 (524gに37g足らず)

となりました。

 この手の問題は、数字の大きい方から順に詰めて試行錯誤すると、大抵の場合うまくいくと
いう話をどこかで読んだことがあります。かなり昔に、容量の小さいフロッピーディスクにサイ
ズがバラバラなファイルをうまく詰め込む方法を知りたくて、そういう考え方のプログラムを作
ったことがありますが、実際うまくいっていました。

 昔作ったプログラムはもしかして今も動く状態で存在するのではないかと思って探したら、
ありました。実行ファイルの日付は1990年4月30日、25年前ですね。

 このプログラムにかけたら、最初の問題は、上記と全く同じでしたが、追加問題では、

 127+106+106+85+84+12=520 、442+37+12+12+10+10=523 、252+252+10+10=524
 252+252+10+10=524 、252+127+127+9+9=524 、252+127+106+37=522
 252+127+106=485

という予想外の結果になりました。(ちょっとアルゴリズムが違うようです。)

 このプログラムがあれば、どんな問題が来ても(手作業で解ける問題なら多分)一発ですね。