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

2023年11月17日13:56:56

假设有一条传送带上有包裹，这些包裹将在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

    • 更新时间：2023年11月17日13:56:56 ，共 1258 字。