Pythonで全員を救出するために必要なロケット船の最小数を求めるプログラム

問題の概要

人々の体重を表す数値のリスト weights と、1台のロケット船に許容される重量制限を示す値 limit が与えられているとします。各ロケット船には最大2人までしか乗せることができません。このとき、全員を惑星へ救出するために必要なロケット船の最小数を求めるのが課題です。

たとえば、入力が weights = [300, 400, 300]、limit = 600 の場合、出力は 2 になります。これは、体重300の2人を1台目のロケット船に乗せ、体重400の人を2台目のロケット船で運ぶためです。

解決のためのステップ

この問題は「貪欲法（グリーディ法）」を用いることで効率的に解けます。具体的には、以下の手順に従います。

• リスト weights を昇順にソートする

• カウンタ cnt := 0 を初期化する

• weights が空になるまで、以下を繰り返す

  • x := weights の末尾の要素（最も重い人）を取り出す

  • weights が空でなく、かつ weights[0] <= limit − x（先頭の最も軽い人が同乗できる場合）ならば、weights の先頭の要素を削除する

  • cnt := cnt + 1 とする

• cnt を返す

なぜこの手法が有効か

最も重い人を必ず1人乗せたうえで、可能であれば最も軽い人をペアとして同乗させることで、各便の積載容量を無駄なく活用できます。この戦略により、必要なロケット船の総数を最小化できます。

実装例（Python）

理解を深めるために、以下のPythonコードをご覧ください。

class Solution:
    def solve(self, weights, limit):
        weights.sort()
        cnt = 0
        while weights:
            x = weights.pop()
            if weights and weights[0] <= limit - x:
                weights.pop(0)
            cnt += 1
        return cnt

ob = Solution()
weights = [300, 400, 300]
limit = 600
print(ob.solve(weights, limit))

入力

[300, 400, 300], 600

出力

2