連載の第 12～15 回では、モノとモノを繋ぐ「グラフ」を使ったアルゴリズムを解説しました。今回は少し話題を変え、アルゴリズムを使って解けるパズル的な問題を 1 つ紹介します。プログラミングを知らない人でも楽しめる問題になっておりますので、ぜひ解いてみてください。

第12回：アルゴリズムの基本用語 - 「グラフ」とは?
第13回：身近な「掃除」を例に考える、「深さ優先探索」とは?
第14回：最短経路を求めるのに便利な「幅優先探索」
第15回：重み付きグラフの問題を解く「ダイクストラ法」

問題

以下の 15 個のおもりがあります。重さの合計は4000gです。「最も重い箱」と「最も軽い箱」の重さの差ができるだけ小さくなるように、おもりを 4 つの箱に入れてください。

ただし、箱の重さは考えなくても良いものとします。

皆さんなら、どういう解法が思い付きますか。少し考えてみましょう。

解法1：順番に入れる

この問題を解く最もシンプルな方法は、「おもりを順番に入れていき、1000g を超えたら次の箱に移る」という方法です。

まず、箱 A には最初の 5 つ（225g・281g・113g・213g・354g）を入れます。この時点で合計が 1000g を超えるので、箱 A に入れるのを止め、箱 B に移ります。

次に、箱 B には 194g・415g・160g・310g の 4 つのおもりを入れます。この時点で合計が 1000g を超えるので、箱 C に移ります。

次に、箱 C には 222g・183g・317g・397g の 4 つのおもりを入れます（この時点で合計が 1000g を超えます）。最後に、残った 2 つのおもりを箱 D に入れると下図のようになり、重さの差が 1186-716=470g となります。

このように、箱 A・B・C 全部について 1000g をギリギリ超えるように入れると、箱 D が 1000g より大幅に小さくなってしまうため、あまりスコアが良くならないようですね。

解法2：4 つずつ入れる

次に、おもりを 4 つずつ入れていくことを考えましょう（おもりの数は 15 個なので、箱 D には 3 個しか入らないことに注意）。すると、最も重い箱の重さは 1123g、最も軽い箱の重さは 832g となります。差は 1123-832=291g であり、前より良い解を出すことができました。