題目
#

leetcode 1011 - Capacity To Ship Packages Within D Days (題目說明請點連結)

題目簡述
#

給定一個包裹重量陣列和運送天數，找到船隻的最小容量，使得所有包裹能在指定的天數內運送完成。

範例
#

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: 船隻容量為 15 時，可以在 5 天內運送所有包裹。

Example 2:

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: 船隻容量為 6 時，可以在 3 天內運送所有包裹。

Example 3:

Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation: 船隻容量為 3 時，可以在 4 天內運送所有包裹。

解題思路
#

這題要求我們找到船隻的最小容量，使得所有包裹能在指定的天數內運送完成。

問題分析
#

給定包裹重量陣列和運送天數
需要找到船隻的最小容量
船隻容量必須大於等於任何單個包裹的重量
返回滿足條件的最小容量

解法：二分搜尋
#

二分搜尋：在可能的容量範圍內搜尋最小容量
可行性檢查：檢查給定容量是否能在指定天數內運送所有包裹
範圍確定：左邊界為最大包裹重量，右邊界為所有包裹重量總和

步驟：

確定搜尋範圍
- 左邊界：最大包裹重量（船隻必須能裝下任何單個包裹）
- 右邊界：所有包裹重量總和（最壞情況）
二分搜尋
- 計算中間容量
- 檢查該容量是否可行
- 根據結果調整搜尋範圍
可行性檢查
- 模擬運送過程
- 計算需要的天數
- 判斷是否在指定天數內完成

例子說明
#

輸入： weights = [1,2,3,4,5,6,7,8,9,10], days = 5

步驟 1：確定搜尋範圍

左邊界：10（最大包裹重量）
右邊界：55（所有包裹重量總和）

步驟 2：二分搜尋

中間容量：32
檢查可行性：需要 3 天，可行
調整範圍：[10, 32]

步驟 3：繼續搜尋

中間容量：21
檢查可行性：需要 4 天，可行
調整範圍：[10, 21]

答案： 15（最小可行容量）

完整程式碼
#

java

import java.util.*;

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0; // 二分搜尋的左右邊界

        // 計算搜尋範圍：左邊界為最大包裹重量，右邊界為所有包裹重量總和
        for (int w : weights) {
            left = Math.max(left, w); // 左邊界必須大於等於任何單個包裹的重量
            right += w; // 右邊界為所有包裹重量總和
        }

        // 二分搜尋最小可行容量
        while (left < right) {
            int mid = left + (right - left) / 2; // 計算中間容量
            if (hasCapacityToShip(days, mid, weights)) { // 檢查該容量是否可行
                right = mid; // 如果可行，嘗試更小的容量
            } else {
                left = mid + 1; // 如果不可行，嘗試更大的容量
            }
        }

        return left; // 返回最小可行容量
    }

    // 檢查給定容量是否能在指定天數內運送所有包裹
    public boolean hasCapacityToShip(int days, int capacity, int[] weights) {
        int need = 1; // 需要的天數，初始為1
        int current = 0; // 當前船隻的載重量

        // 模擬運送過程
        for (int w : weights) {
            // 如果加上當前包裹會超過容量，需要新的一天
            if (current + w > capacity) {
                current = 0; // 重置載重量
                need++; // 天數加1
            }
            current += w; // 將包裹加入船隻
        }

        return need <= days; // 判斷是否在指定天數內完成
    }
}