ซื้อรถให้ได้มากที่สุดในงบประมาณ Python

ภาพรวม

โจทย์หาจำนวนรถสูงสุดที่ซื้อได้จากรายการราคา โดยมีงบประมาณ k กลยุทธ์คือซื้อรถราคาถูกก่อน (Greedy)

ตัวอย่าง

ราคา: [80, 20, 10, 30, 80], งบ 85

เรียงราคา: [10, 20, 30, 80, 80]

ซื้อ: 10 (เหลือ 75), 20 (เหลือ 55), 30 (เหลือ 25) → หยุด เพราะ 80 > 25

ซื้อได้ 3 คัน

โค้ด Python

class Solution:
    def solve(self, prices, k):
        count = 0
        prices.sort()
        for price in prices:
            if price <= k:
                k -= price
                count += 1
            else:
                break
        return count

ob = Solution()
p = [80, 20, 10, 30, 80]
print(ob.solve(p, 85))

หลักการ Greedy

การซื้อของราคาถูกก่อนจะให้จำนวนชิ้นส่วนมากที่สุดเสมอ (optimal substructure) เนื่องจากทุกคันมี "ค่า" เท่ากัน (1 คัน) แต่ "ราคา" ต่างกัน

ความซับซ้อน

• เวลา: O(n log n) จากการ sort
• พื้นที่: O(1) เพิ่มเติม (sort in-place)

ผลลัพธ์

3