โปรแกรมค้นหาหลายวิธีที่เราจะได้รับ n R.s โดยใช้นิกายอินเดียใน Python

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

ดังนั้น หากอินพุตเท่ากับ n =25 count =[7,3,2,2] เอาต์พุตจะเป็น 9

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

• ค่า :=[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] * (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 = 25
count = [7,3,2,2]
print(solve(n, count))

อินพุต

25, [7,3,2,2]

ผลลัพธ์

9