โปรแกรม Python เพื่อหาวิธีรับ n รูปีด้วยเหรียญที่กำหนด

สมมติว่าเราได้ให้เหรียญนิกาย (1, 2, 5 และ 10) เราต้องหาว่าเราจะจัด n โดยใช้การปกครองเหล่านี้ได้กี่วิธี เรามีอาร์เรย์ที่เรียกว่า count มี 4 องค์ประกอบ โดยที่ count[0] ระบุจำนวนเหรียญ 1, count[1] ระบุจำนวนเหรียญสำหรับ 2 เป็นต้น

ดังนั้น หากอินพุตมีค่าเท่ากับ n =27 count =[8,4,3,2] ผลลัพธ์จะเป็น 18 ดังนั้นจึงมีชุดค่าผสมที่เป็นไปได้ 18 ค่าบางค่า

• 10*2 + 5*1 + 2*1 =27

• 10*2 + 2*3 + 1*1 =27

• 10*1 + 5*3 + 2*1 =27

• 10*1 + 5*1 + 4*2 + 4*1 =27

และอื่นๆ...

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ค่า :=[1,2,5,10]
• A :=อาร์เรย์ของขนาด (n + 1) และเติมด้วย 0
• B :=รายการใหม่จาก A
• สำหรับ i ในช่วง 0 ถึง (จำนวนขั้นต่ำ[0] และ n) ทำ
  • A[i] :=1
• สำหรับผมในช่วง 1 ถึง 3 ทำ
  • สำหรับ j ในช่วง 0 เพื่อนับ[i] ทำ
    • สำหรับ k ในช่วง 0 ถึง n + 1 - j *denom[i], do
      • B[k + j * denom[i]] :=B[k + j * denom[i]] + A[k]
  • สำหรับ j ในช่วง 0 ถึง n ทำ
    • A[j] :=B[j]
    • B[j] :=0
• ส่งคืน A[n]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

denom = [1,2,5,10]

def solve(n, count):
   A = [0 for _ in range(n+1)]
   B = list(A)
   for i in range(min(count[0], n) + 1):
      A[i] = 1
   for i in range(1, 4):
      for j in range(0, count[i] + 1):
         for k in range(n + 1 - j *denom[i]):
            B[k + j * denom[i]] += A[k]
      for j in range(0, n + 1):
         A[j] = B[j]
         B[j] = 0
   return A[n]

n = 27
count = [8,4,3,2]
print(solve(n, count))

อินพุต

27, [8,4,3,2]

ผลลัพธ์

18