用 Python 计算 D 天内运送包裹的能力

pythonserver side programmingprogramming更新于 2025/11/14 15:40:17

假设有一条传送带，上面有包裹，这些包裹将在 D 天内从一个港口运送到另一个港口。这里，传送带上的第 i 个包裹的重量为 weights[i]。每天，我们都会将传送带上的包裹装上船。我们装载的重量不会超过船的最大承重能力。我们必须找到船的最小承重能力，使传送带上的所有包裹都能在 D 天内运送出去。因此，如果输入为 [3,2,2,4,1,4] 且 D = 3，则输出将为 6，因为船舶容量为 6 是 3 天内运送所有包裹的最低要求，如 −

第 1 天:3、2
第 2 天:2、4
第 3 天:1、4

为了解决这个问题，我们将遵循以下步骤 −

定义一个递归函数solve()。这将采用权重数组、maxWeight 和船只数组，其作用类似于 −
index := 0
for i in range 0 to length of ship array
- ships[i] := 0
- while index <权重的长度和ships[i] + weights[index] <= maxWeight
  - ships[i] := ship[i] + weights[index]
  - 将索引增加 1
当 index = 权重的长度时返回 true，否则返回 false
main 方法的作用如下
ships := 与 D 大小相同的数组，并用 0 填充
maxWeight := 权重的最大值
low := maxWeight，high := maxWeight + 权重数组的长度 + 1
当 low < high
- mid := low + (high - low)/2
- 如果solve(weights, mid, ship)为真，则high := mid，否则low := mid + 1
return 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))