経緯

後輩から以下のようなLINEがきました。

後輩からのLINE

「適切」という言葉が曖昧だが、以下のように解釈しました。

  1. 材料の本数が最小であること。
  2. 最後、余る棒の長さが最大であること。

要は、あまり材料を使わず、しかも、あまりを使いまわせるように出来る限り、長く取ろうという話。

とりあえず、俺なりの回答

Rubyで総当りのプログラムを作りました。ちょっと無駄は多いけど、まぁ、ひとまず動くのでいいかなと思います。

出力はこんなかんじ。

出力

考察

この問題は部分和問題の類似問題かなーと思いました。

部分和問題とは、たとえば

[1,4,5,9]を適当に組み合わせて和が12になるようにできるか?

というような問題。この場合は、回答はNoです。どれだけ頑張っても12は作れません。

今回の問題はピッタリになることは通常ないと思うので、12以下の最大の値を作るためにはどうすればいいか?という話です。

たぶん、動的計画法に類似した方法になっているのかなーと思います。