資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究Python 中 D 天內運送包裹的能力
假設有一條傳送帶，上面裝著需要在 D 天內從一個港口運送到另一個港口的包裹。傳送帶上第 i 個包裹的重量為 weights[i]。每天，我們將用傳送帶上的包裹裝載船隻。我們裝載的重量不會超過船舶的最大重量承載能力。我們必須找到能夠在 D 天內運送傳送帶上所有包裹的船舶的最小重量承載能力。因此，如果輸入像 [3,2,2,4,1,4] 並且 D = 3，則輸出將為 6，因為 6 的船舶承載能力是在 3 天內運送所有包裹的最小值，例如：
第一天：3, 2
第二天：2, 4
第三天：1, 4
為了解決這個問題，我們將遵循以下步驟：
定義一個遞迴函式 solve()。這將接收 weights 陣列、maxWeight 和 ships 陣列，這將起作用：
index := 0
for i in range 0 to length of ships array
ships[i] := 0
while index < length of weights and 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 + weights 陣列的長度 + 1
while low < high
mid := low + (high - low)/2
如果 solve(weights, mid, ships) 為 true，則 high := mid，否則 low := mid + 1
返回 high
讓我們看看下面的實現以更好地理解：
示例
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
251 次瀏覽
