使用Python在D天内运送包裹的能力

假设有一条传送带上有包裹，这些包裹将在D天之内从一个港口运到另一个港口。此处，传送带上的第i个包装的重量为砝码[i]。每天，我们都会在皮带上向船上装载包裹。我们装载的重量不会超过船舶的最大承重量。我们必须找到最小的船舶重量，这将导致在D天之内运送完传送带上的所有包裹。因此，如果输入为[3,2,2,4,1,4]且D = 3，则输出将为6，因为6的装船量是3天内运送所有包裹的最小值-

• 第1天，3、2

• 第2天，2、4天

• 第3天，1、4天

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

• 定义一个递归函数solve()。这将采用weights数组，maxWeight和ships数组，其作用类似于-

• 索引：= 0

• 对于范围在0到舰船长度范围内的i

• 船舶[i]：=船舶[i] +重量[索引]

• 指数增加1

• 船只[i]：= 0

• 而索引<重量和船只的长度[i] +重量[索引] <= maxWeight

• 当index =权重长度时返回true，否则返回false

• 主要方法会像

• 船：=大小与D相同的数组，并用0填充

• maxWeight：=最大重量

• 低：= maxWeight，高：= maxWeight +权重数组的长度+ 1

• 从低到高

• 中：=低+（高-低）/ 2

• 如果solve(weights,mid,ships)为true，则为高：=中，否则为低：=中+1

• 高回报

让我们看下面的实现以更好地理解-

示例

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