Giả sử chúng ta có một mảng được gọi là xu với n phần tử và nó đại diện cho số xu mà chúng ta sở hữu. Giá trị của đồng tiền thứ i được ký hiệu là xu [i]. Chúng ta có thể tạo ra một số giá trị x nếu chúng ta có thể chọn một số trong số n đồng xu sao cho giá trị của chúng bằng x. Chúng tôi phải tìm số lượng giá trị liên tiếp tối đa mà chúng tôi có thể nhận được với các đồng tiền bắt đầu từ và bao gồm cả 0.
Vì vậy, nếu đầu vào giống như xu =[1,1,3,4], thì đầu ra sẽ là 10, bởi vì
-
0 =[]
-
1 =[1]
-
2 =[1,1]
-
3 =[3]
-
4 =[4]
-
5 =[4,1]
-
6 =[4,1,1]
-
7 =[4,3]
-
8 =[4,3,1]
-
9 =[4,3,1,1]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sắp xếp các đồng tiền trong danh sách
-
ans:=1
-
đối với mỗi đồng xu, hãy thực hiện
-
if coin> ans, then
-
đi ra từ vòng lặp
-
-
ans:=ans + xu
-
-
trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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