สมมติว่ามีสายพานลำเลียงที่มีบรรจุภัณฑ์ที่จะจัดส่งจากท่าเรือหนึ่งไปยังอีกที่หนึ่งภายใน 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() การดำเนินการนี้จะรับอาร์เรย์น้ำหนัก, maxWeight และอาร์เรย์ของการจัดส่ง ซึ่งจะทำหน้าที่เหมือน −
-
ดัชนี :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึงความยาวของอาร์เรย์เรือรบ
-
เรือ[i] :=0
-
ในขณะที่ดัชนี <ความยาวของน้ำหนักและเรือ[i] + น้ำหนัก[ดัชนี] <=maxWeight
-
เรือ[i] :=เรือ[i] + น้ำหนัก[ดัชนี]
-
เพิ่มดัชนีขึ้น 1
-
-
-
คืนค่า จริง เมื่อ index =ความยาวของน้ำหนัก มิฉะนั้น เท็จ
-
วิธีการหลักจะทำหน้าที่เหมือน
-
ships :=อาร์เรย์ที่มีขนาดเท่ากับ D และเติมด้วย 0
-
maxWeight :=น้ำหนักสูงสุด
-
ต่ำ :=maxWeight สูง :=maxWeight + ความยาวของน้ำหนักอาร์เรย์ + 1
-
ในขณะที่ต่ำ <สูง
-
กลาง :=ต่ำ + (สูง - ต่ำ)/2
-
ถ้าแก้(น้ำหนัก กลาง เรือรบ) เป็นจริง แล้วสูง :=กลาง หรือต่ำ :=กลาง + 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
