สมมติว่าเรามีรายการค่าที่เรียกว่า coins และอีกรายการหนึ่งเรียกว่าปริมาณที่เท่ากัน มูลค่าของเหรียญ ith คือ coins[i] และขณะนี้เรามีจำนวนเหรียญ ith ในปริมาณ[i] เราต้องหาจำนวนค่ารวมของเหรียญที่แตกต่างกันที่เราหาได้โดยใช้กลุ่มที่ไม่ว่างเปล่าของเหรียญเหล่านี้
ดังนั้น หากการป้อนเป็นเหมือนเหรียญ =[1, 2, 5] ปริมาณ =[1, 2, 1] ผลลัพธ์จะเป็น 10 เนื่องจากเราสามารถมีผลรวมเหรียญที่แตกต่างกันดังต่อไปนี้ [1] =1, [2] =2, [1,2] =3, [2,2] =4, [5] =5, [1,5] =6, [2,5] =7, [1,2,5] =8 , [2,2,5] =9, [1,2,2,5] =10.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
กำหนดฟังก์ชัน rec() นี่จะใช้เวลา i, res
if i is same as size of coins , then return for k in range 0 to quantities[i] + 1, do cur := res + k * coins[i] insert cur into fres rec(i + 1, cur) From the main method, do the following: fres := a new set rec(0, 0) return size of fres - 1
ตัวอย่าง
class Solution: def solve(self, coins, quantities): def rec(i, res): if i == len(coins): return for k in range(0, quantities[i] + 1): cur = res + k * coins[i] fres.add(cur) rec(i + 1, cur) fres = set() rec(0, 0) return len(fres) - 1 ob = Solution() coins = [1, 2, 5] quantities = [1, 2, 1] print(ob.solve(coins, quantities))
อินพุต
[1, 2, 5], [1, 2, 1]
ผลลัพธ์
10
