โปรแกรม Python สำหรับ Coin Change (ปัญหาเงินทอน)

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — กำหนดเหรียญ N เหรียญ และเราต้องการทำเงินทอนของเหรียญเหล่านั้น โดยที่มีสินค้าคงคลังไม่จำกัดของแต่ละค่าใน S ให้แสดงว่าเราสามารถทำเงินทอนได้กี่วิธี โดยไม่คำนึงถึงลำดับ

เราจะใช้แนวคิด Dynamic Programming เพื่อแก้ปัญหาและลดความซับซ้อนด้านเวลา

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

# วิธี Dynamic Programming
def count(S, m, n):
    # กรณีฐาน
    table = [[0 for x in range(m)] for x in range(n+1)]
    # สำหรับ n=0
    for i in range(m):
        table[0][i] = 1
    # เติมค่าส่วนที่เหลือแบบ bottom-up
    for i in range(1, n+1):
        for j in range(m):
            # วิธีที่รวม S[j]
            x = table[i - S[j]][j] if i - S[j] >= 0 else 0
            # วิธีที่ไม่รวม S[j]
            y = table[i][j-1] if j >= 1 else 0
            # รวมทั้งหมด
            table[i][j] = x + y
    return table[n][m-1]

# โปรแกรมหลัก
arr = [1, 3, 2, 4]
m = len(arr)
n = 5
print("Number of coins:", end="")
print(count(arr, m, n))

ผลลัพธ์

Number of coins: 6

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ Coin Change โดยใช้ Dynamic Programming