โปรแกรมหาจำนวนยานขนส่งน้อยที่สุดสำหรับการช่วยชีวิตใน Python

สมมติว่าเรามีรายการตัวเลข weights แสดงน้ำหนักของคน และค่า limit เป็นน้ำหนักสูงสุดของยานขนส่งหนึ่งลำ แต่ละลำรับคนได้สูงสุด 2 คน เราต้องหาจำนวนยานขนส่งน้อยที่สุดเพื่อช่วยคนทุกคน

ตัวอย่าง: weights = [300, 400, 300], limit = 600 ผลลัพธ์คือ 2 (ลำหนึ่งรับคนน้ำหนัก 300 สองคน, อีกลำรับคนน้ำหนัก 400)

ขั้นตอนการแก้ปัญหา

1. เรียงลำดับ weights
2. กำหนด cnt = 0
3. วนลูป while weights ไม่ว่าง:
   • x = weights.pop() (นำคนหนักที่สุดออก)
   • ถ้า weights ไม่ว่าง และ weights[0] <= limit - x:
     • weights.pop(0) (นำคนเบาที่สุดออกไปด้วย)
   • cnt += 1
4. คืนค่า cnt

ตัวอย่างโค้ด 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))  # Output: 2

อินพุต / เอาต์พุต

Input: [300, 400, 300], 600

Output: 2