1011. Capacity To Ship Packages Within D Days

Last updated on Dec 7, 2025

題目給定一個陣列內含沒有排序的正整數以及一個數字代表天數。

這個陣列的意義是總共有 n 個正整數，每個數字是包裹的重量，排列的順序代表要寄送的順序，天數是我們需要在這個天數內把所有的包裹寄送完。

題目所要求的是找出一個貨櫃，該貨櫃有一定的容量，在規定的天數內分批運送完這些這些貨物，並且我們要找出這個容量的最小值。

這個題目乍看之下很像是需要動態規劃的題目，因為很像是要透過不同的組合去找出一個極值。但是仔細想想後發現動態規劃找不太到動態規劃的轉移方程式。

因為題目有規定包裹要依序寄送，找尋答案的過程中並不存在著子問題的情況，因此動態規劃並不一定適合。

這時候需要多觀察一下題目，首先既然要找出貨櫃的最小容量，代表的是我們應該要用盡所有的天數來寄送所有包裹，可以這樣證明，因為如果還有天數可以寄送，那就代表某一天的包裹可以分拆成兩天，那需要的貨櫃最小容量就可以再更少。

接著這個貨櫃的大小有沒有範圍限制？答案是有的

最小的貨櫃可以有多小呢？最小的貨櫃需要滿足：最少要裝一個貨物，而這個貨物至少要是這些貨物中最重的貨物的重量，因為如果容量比最重的貨物還小，那就會裝不進去這個貨物，就不可能滿足題目的條件。

而最大的貨櫃可以多大呢？最大的貨櫃則是可以把所有的貨物都裝在一起，也就是所有貨物的重量的總和，如果天數剛好是一天內要寄完，那這個貨櫃剛好就裝下所有的東西。

透過以上貨櫃的觀察，我們可以把貨櫃的大小限制在以下的範圍：

$$ max(weights) <= capacity <= sum(weights) $$

我們的目標就是找到 $capacity $，這時候題目才會比較明朗化，在一個範圍要找到一個滿足條件的目標值，最好的方法其實就是二分搜索，在這個題目其實感覺也很合理，例如：我在這個範圍中間切一刀，接著看看我需要花幾天來搬完所有的東西，如果說我需要花的天數大於題目給的天數，那就代表這個貨櫃的容量太小的，我要再增加我的容量，如果我需要花費的天數少於獲釋等於所需要花費的天數，那就代表容積太大了，我可以往容積更小的方向來搜尋。

至此，題目所欠缺的便是給定貨櫃的容積，如何成功計算出所需要花費的天數了。

這個天數好算是因為題目有給定寄送的方式，那就是每次貨櫃盡量裝，如果裝滿了，那就多加一天，重新裝載。

組合起來後即是二分搜索的變形：

from typing import List

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        
        # 輔助函式：計算給定承載能力所需天數
        def calculate_days(capacity: int) -> int:
            total_days = 1 # 至少需要一天
            current_load = 0
            for weight in weights:
                # 如果加上這個包裹會超過容量，則這包裹必須在下一天運送
                if current_load + weight > capacity:
                    current_load = weight
                    total_days += 1
                else:
                    current_load += weight
            return total_days
        
        # 搜尋區間：[最小承載力, 最大承載力]
        left = max(weights)        # 最小：船至少要能裝最重的包裹
        right = sum(weights)       # 最大：船能一次裝載所有包裹 (只需 1 天)

        # 尋找滿足條件的最小承載力
        while left <= right:
            mid = left + (right - left) // 2
            
            # 檢查 mid 容量所需的天數
            days_needed = calculate_days(mid)
            
            if days_needed > days:
                # 容量 mid 太小，導致所需天數太多
                # 排除 mid 及其左側
                left = mid + 1
            else:
                # 容量 mid 足夠 (days_needed <= days)，mid 可能是答案
                # 記錄潛在答案，並嘗試尋找更小的容量
                right = mid - 1
        
        # 迴圈結束時，left 指向第一個滿足條件的最小容量
        return left