โปรแกรมหาจำนวนค่าต่อเนื่องสูงสุดที่ทำได้จากเหรียญใน Python

สมมติว่ามีอาร์เรย์ coins แทนเหรียญที่มี เราสามารถสร้างค่า x ได้ถ้าเลือกเหรียญบางส่วนรวมกันได้ x ต้องหาจำนวนค่าต่อเนื่องสูงสุดตั้งแต่ 0 ที่ทำได้

ตัวอย่าง: coins = [1,1,3,4] ผลลัพธ์ 10 (ทำได้ 0..9)

วิธีแก้ปัญหา (Greedy)

1. เรียง coins
2. ans := 1
3. วน coin ใน coins:
   • ถ้า coin > ans: break
   • ans += coin
4. คืน ans

เหตุผล: ถ้าทำค่า 0..ans-1 ได้ และเหรียญถัดไป ≤ ans ก็ทำ 0..ans+coin-1 ได้

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

def solve(coins):
    coins.sort()
    ans = 1
    for coin in coins:
        if coin > ans:
            break
        ans += coin
    return ans

coins = [1,1,3,4]
print(solve(coins))

อินพุต

[1,1,3,4]

เอาต์พุต

10