1011. Capacity To Ship Packages Within D Days

Last updated on Aug 14, 2024

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        
        def weighting(capacity):
            total = 1
            acc = 0
            for weight in weights:
                if acc + weight > capacity:
                    # 該重量不計入今天的計算，但是計入明天的計算
                    acc = weight
                    # 明天
                    total += 1
                else:
                    acc += weight
            return total
        
        left = max(weights)
        right = sum(weights) + 1

        while left < right:
            mid = left + (right - left) // 2
            if weighting(mid) <= days:
                right = mid 
            else:
                left = mid + 1
        
        return left