PythonでD日以内に全パッケージを発送する最小積載容量を二分探索で求める方法

ベルトコンベア上に、D日以内に港から別の港へ発送しなければならない荷物が流れてくるとします。コンベア上のi番目の荷物の重さは weights[i] で表されます。毎日、このコンベアから船へ荷物を積み込みますが、船の最大積載重量を超えて積むことはできません。ここで求めたいのは、コンベア上のすべての荷物をD日以内に発送し切るために必要な、船の最小積載容量です。

たとえば、入力が [3,2,2,4,1,4]、D = 3 の場合、出力は 6 になります。これは、3日間ですべての荷物を発送するには容量6の船が最低限必要だからです。具体的な積み込み方は以下のようになります。

• 1日目：3, 2

• 2日目：2, 4

• 3日目：1, 4

解法のアプローチ：二分探索

この問題は二分探索（バイナリサーチ）を使うことで効率的に解けます。答えとなる容量の候補範囲を半分ずつ絞り込みながら、「その容量であればD日以内に発送可能か？」という判定を繰り返していくのがポイントです。

判定関数 solve() の設計

まず、指定した容量で実際にすべての荷物を積み込めるかを判定する関数 solve() を定義します。引数として weights 配列、maxWeight（仮の容量）、ships 配列を受け取ります。

• index := 0 と初期化する

• i を 0 から ships 配列の長さまで繰り返す

  • ships[i] := 0 とする

  • index < weights の長さ かつ ships[i] + weights[index] <= maxWeight の間、次を繰り返す

    • ships[i] := ships[i] + weights[index]

    • index を 1 増やす

• index == weights の長さになれば true を返し、そうでなければ false を返す

メイン処理の流れ

• ships := サイズ D の配列を作成し、0 で初期化する

• maxWeight := weights の最大値（これが下限）

• low := maxWeight、high := maxWeight × 荷物の総数 + 1（十分な上限）とする

• low < high の間、次を繰り返す

  • mid := low + (high − low) / 2

  • solve(weights, mid, ships) が true なら high := mid、そうでなければ low := mid + 1

• 最後に high を返す（これが最小積載容量）

判定が成功すれば上限を mid に下げ、失敗すれば下限を mid + 1 に上げることで、条件を満たす最小値へと収束させています。

実装例

class Solution(object):
    def shipWithinDays(self, weights, D):
        ships = [0 for i in range(D)]
        max_w = max(weights)
        low = max_w
        high = max_w * len(weights)+1
        while low<high:
            mid = low + (high-low)//2
            if self.solve(weights,mid,ships):
                high = mid
            else:
                low = mid+1
        return high
    def solve(self,weights,max_w,ships):
        index = 0
        for i in range(len(ships)):
            ships[i] = 0
            while index < len(weights) and ships[i]+weights[index]<= max_w:
                ships[i] += weights[index]
                index+=1
        return index == len(weights)
ob = Solution()
print(ob.shipWithinDays([3,2,2,4,1,4],3))

入力

[3,2,2,4,1,4]
3

出力

6