สมมติว่าเรามีอาร์เรย์ที่เรียกว่าเหรียญที่มีองค์ประกอบ n และเป็นตัวแทนของเหรียญที่เราเป็นเจ้าของ มูลค่าของเหรียญ ith แสดงเป็น coins[i] เราสามารถสร้างมูลค่า x ได้ หากเราสามารถเลือกเหรียญ n ของเราได้บางส่วน โดยที่ค่าของพวกมันรวมกันได้ x เราต้องหาจำนวนค่าต่อเนื่องสูงสุดที่เราจะได้เหรียญตั้งแต่ 0 ขึ้นไป
ดังนั้นหากอินพุตเป็นเหมือนเหรียญ =[1,1,3,4] ผลลัพธ์จะเป็น 10 เพราะ
-
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]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เรียงเหรียญตามรายการ
-
ตอบ :=1
-
สำหรับเหรียญแต่ละเหรียญให้ทำ
-
ถ้าเหรียญ> ans แล้ว
-
ออกจากวง
-
-
ans :=ans + เหรียญ
-
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
