โปรแกรมหาจำนวน Ice Cream Bars สูงสุดที่ซื้อได้ใน Python

ปัญหา

อาร์เรย์ costs ราคาไอศกรีมแต่ละแท่ง มีเหรียญ c ต้องการซื้อเยอะที่สุด หา Max จำนวนแท่ง

ตัวอย่าง

costs = [3,1,4,5,2], c = 10 → Output: 4

ซื้อ Index 0,1,2,4: 3+1+4+2 = 10

อัลกอริทึม (Greedy Sort)

1. Sort Costs เรียงน้อยไปมาก
2. ซื้อจากถูกไปแพ้จนเงินไม่พอ

ตัวอย่างโค้ด

def solve(costs, c):
    costs.sort()
    i = 0
    while i < len(costs) and c >= costs[i]:
        c -= costs[i]
        i += 1
    return i

costs = [3,1,4,5,2]
c = 10
print(solve(costs, c))  # 4

ความซับซ้อน

• Time: O(n log n) จาก Sort
• Space: O(1) In-place Sort

Greedy Optimal: ซื้อของถูกก่อนได้จำนวนมากที่สุดเสมอ (Matroid Property)