Chương trình tìm số lượng tên lửa tối thiểu cần thiết để cứu hộ bằng Python

Giả sử chúng ta có một danh sách các số được gọi là trọng lượng, đây là đại diện cho trọng lượng của mọi người và giới hạn giá trị xác định giới hạn trọng lượng của một tàu tên lửa. Bây giờ mỗi tên lửa có thể chở nhiều nhất hai người. Chúng tôi phải tìm ra số lượng tàu tên lửa tối thiểu cần thiết để giải cứu tất cả mọi người đến Planet.

Vì vậy, nếu đầu vào giống như trọng lượng =[300, 400, 300], giới hạn =600, thì đầu ra sẽ là 2, vì một tàu tên lửa sẽ lấy hai người có trọng lượng mỗi người là 300 và người khác lấy người có trọng lượng 400.

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

• sắp xếp trọng số danh sách

• cnt:=0

• trong khi trọng số là không rỗng, thực hiện

  • x:=xóa phần tử cuối cùng khỏi trọng số

  • nếu trọng số không trống và trọng số [0] <=limit - x thì

    • xóa phần tử đầu tiên khỏi trọng số

  • cnt:=cnt + 1

• trả lại cnt

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

Ví dụ (Python)

class Solution:
def solve(self, weights, limit):
   weights.sort()
   cnt = 0
   while weights:
      x = weights.pop()
      if weights and weights[0] <= limit - x:
         weights.pop(0)
      cnt += 1
   return cnt
ob = Solution()
weights = [300, 400, 300]
limit = 600
print(ob.solve(weights, limit))

Đầu vào

[300, 400, 300], 600

Đầu ra

2