数据结构
网络
关系数据库管理系统 (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 次浏览
