Chương trình tìm số giá trị liên tiếp tối đa có thể tạo được từ đồng xu trong Python

Mô tả bài toán

Cho mảng coins biểu diễn giá trị các đồng xu. Có thể tạo giá trị x nếu chọn một tập con đồng xu có tổng bằng x. Tìm số lượng giá trị liên tiếp tối đa bắt đầu từ 0 có thể tạo được.

Ví dụ

Nếu coins = [1,1,3,4], đầu ra là 10 vì có thể tạo các giá trị 0 đến 9.

Giải thuật

1. Sắp xếp mảng coins.
2. Khởi tạo ans = 1 (có thể tạo được giá trị từ 0 đến ans-1).
3. Duyệt từng coin:
   • Nếu coin > ans: dừng lại (không thể tạo giá trị ans).
   • Ngược lại: ans += coin (mở rộng phạm vi tạo được).
4. Trả về ans.

Triển khai Python

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))

Đầu vào

[1,1,3,4]

Đầu ra

10