Năng lực vận chuyển các gói hàng trong vòng D ngày bằng Python

Giả sử có một băng chuyền có các gói hàng sẽ được chuyển từ cảng này sang cảng khác trong vòng D ngày. Ở đây kiện hàng thứ i trên băng tải có khối lượng là các quả cân [i]. Mỗi ngày, chúng tôi sẽ tải tàu với các gói hàng trên vành đai. Chúng tôi sẽ không tải trọng lượng lớn hơn trọng lượng tối đa của tàu. Chúng ta phải tìm khả năng có trọng lượng nhỏ nhất của con tàu để tất cả các gói hàng trên băng chuyền sẽ được vận chuyển trong vòng D ngày. Vì vậy, nếu đầu vào là [3,2,2,4,1,4] và D =3, thì đầu ra sẽ là 6, vì công suất tàu 6 là mức tối thiểu để vận chuyển tất cả các gói hàng trong 3 ngày, như -

• Ngày 1:3, 2

• Ngày 2:2, 4

• Ngày 3:1, 4

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm đệ quy giải quyết (). Điều này sẽ lấy mảng trọng số, maxWeight và mảng tàu, điều này sẽ hoạt động như thế -

• chỉ mục:=0

• cho tôi trong phạm vi từ 0 đến chiều dài của mảng tàu

  • tàu [i]:=0

  • while index

    • ship [i]:=ship [i] + weights [index]

    • tăng chỉ số lên 1

• trả về true, khi index =length of weights, ngược lại là false

• Phương thức chính sẽ hoạt động giống như

• ship:=một mảng có kích thước giống như D và điền nó bằng 0

• maxWeight:=tối đa trọng lượng

• low:=maxWeight, high:=maxWeight + length of weights array + 1

• trong khi thấp

  • giữa:=low + (cao - thấp) / 2

  • nếu giải quyết (weights, mid, ship) là true thì high:=mid, ngược lại low:=mid + 1

• trả lại cao

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[3,2,2,4,1,4]
3

Đầu ra

6