ปัญหาการทอนเงินเป็นปัญหาที่ต้องหาจำนวนเหรียญขั้นต่ำ (ใน denominations ที่กำหนด) ที่รวมกันแล้วได้จำนวนเงินที่กำหนดให้ เป็นกรณีพิเศษของปัญหาเป้สะพาย หลังจำนวนเต็ม และมีการประยุกต์ใช้ที่กว้างขวางกว่าแค่เรื่องเงินตรา

นอกจากนี้ ยังเป็นรูปแบบที่พบได้บ่อยที่สุดของปัญหาการทอนเงินซึ่งเป็นกรณีทั่วไปของการแบ่งส่วนโดยที่เมื่อกำหนดมูลค่า ของเหรียญ จำนวนอนันต์ มาให้แล้ว เป้าหมายคือการหาจำนวนวิธีที่เป็นไปได้ในการทอนเงินจำนวนหนึ่งโดยไม่คำนึงถึงลำดับของเหรียญ

เป็นปัญหา NP-hard ที่ไม่รุนแรงนักแต่สามารถแก้ไขได้อย่างเหมาะสมในเวลาพсевдоพหุนามโดยใช้ การ เขียนโปรแกรมแบบไดนามิก^{[ 1 ] [ 2 ]}

ค่าของเหรียญสามารถจำลองได้ด้วยชุดของ ค่า จำนวนเต็มบวกที่แตกต่างกันnค่า (จำนวนเต็ม) เรียงลำดับจากน้อยไปมากเป็นw ₁ถึงw _nปัญหาคือ: กำหนดจำนวนเงินWซึ่งเป็นจำนวนเต็มบวกเช่นกัน ต้องหาชุดของจำนวนเต็มที่ไม่เป็นลบ (บวกหรือศูนย์) { x ₁ , x ₂ , ..., x _n } โดยที่ x _jแต่ละตัวแทนความถี่ในการใช้เหรียญที่มีมูลค่าw _jซึ่งจะทำให้จำนวนเหรียญทั้งหมดf ( W ) น้อยที่สุด

${\displaystyle f(W)=\sum _{j=1}^{n}x_{j}}$

ขึ้นอยู่กับ

${\displaystyle \sum _{j=1}^{n}w_{j}x_{j}=W.}$

ตัวอย่างการประยุกต์ใช้ปัญหาการเปลี่ยนแปลงค่าต่างๆ สามารถพบได้ในการคำนวณวิธีการต่างๆ ที่จะทำให้ได้คะแนนเก้าแต้มในการเล่นปาลูกดอก

อีกหนึ่งการประยุกต์ใช้คือ การคำนวณองค์ประกอบอะตอม (หรือไอโซโทป) ที่เป็นไปได้ของยอดมวล/ประจุที่กำหนดในสเปกโทรเมตรีมวล

กลยุทธ์ การเขียนโปรแกรมแบบไดนามิกคลาสสิกทำงานจากล่างขึ้นบนโดยการค้นหาชุดค่าผสมของค่าที่เล็กกว่าทั้งหมดที่จะรวมกันเป็นค่าเกณฑ์ปัจจุบัน^{[ 3 ]}ดังนั้น ในแต่ละเกณฑ์ ค่าเกณฑ์ก่อนหน้าทั้งหมดจะถูกพิจารณาเพื่อทำงานจากล่างขึ้นบนไปยังจำนวนเป้าหมายWด้วยเหตุนี้ วิธีการเขียนโปรแกรมแบบไดนามิกนี้จึงต้องการจำนวนขั้นตอนที่เป็น O( nW)โดยที่nคือจำนวนประเภทของเหรียญ

ต่อไปนี้เป็นตัวอย่างการใช้งานการเขียนโปรแกรมเชิงพลวัต (ด้วย Python 3) ซึ่งใช้เมทริกซ์ในการติดตามคำตอบที่ดีที่สุดของปัญหาย่อย และส่งคืนจำนวนเหรียญขั้นต่ำ หรือ "อนันต์" หากไม่มีวิธีใดที่จะทอนเงินด้วยเหรียญที่กำหนดให้ อาจใช้เมทริกซ์ที่สองเพื่อหาชุดเหรียญสำหรับคำตอบที่ดีที่สุด

def _get_change_making_matrix ( set_of_coins , r : int ): m = [[ 0 for _ in range ( r + 1 )] for _ in range ( len ( set_of_coins ) + 1 )] for i in range ( 1 , r + 1 ): m [ 0 ][ i ] = float ( "inf" ) # โดยค่าเริ่มต้นจะไม่มีวิธีการทอนเงินคืนค่าmdef change_making ( coins , n : int ): """ฟังก์ชันนี้สมมติว่าเหรียญทั้งหมดมีอยู่ไม่จำกัด หากใช้เหรียญเพียงครั้งเดียว ให้เปลี่ยน m[c][r - coin] เป็น m[c - 1][r - coin]  n คือจำนวนที่ต้องการโดยใช้เหรียญน้อยที่สุด coins คือลิสต์หรือทูเปิลที่มีมูลค่าเหรียญที่มีอยู่ """ m = _get_change_making_matrix ( coins , n ) for c , coin in enumerate ( coins , 1 ): for r in range ( 1 , n + 1 ): # ใช้เหรียญนั้นเลยถ้าcoin == r : m [ c ][ r ] = 1 # ไม่สามารถรวม coin ได้# ใช้วิธีแก้ปัญหาก่อนหน้าสำหรับการสร้าง r # โดยไม่รวม coin elif coin > r : m [ c ][ r ] = m [ c - 1 ][ r ] # สามารถใช้ coin ได้# ตัดสินใจว่าวิธีแก้ปัญหาใดต่อไปนี้ดีที่สุด: # 1. ใช้วิธีแก้ปัญหาเดิมในการสร้าง r (โดยไม่ต้องใช้เหรียญ) # 2. ใช้วิธีแก้ปัญหาเดิมในการสร้าง r - เหรียญ (โดยไม่ใช้เหรียญ) บวกกับเหรียญพิเศษอีก 1 เหรียญมิเช่น นั้น : m [ c ][ r ] = min ( m [ c - 1 ][ r ], 1 + m [ c ][ r - coin ]) คืนค่าm [ - 1 ][ - 1 ]

สำหรับระบบเหรียญกษาปณ์ในโลกแห่งความเป็นจริงหลายๆ ระบบ เช่น ระบบที่ใช้ในสหรัฐอเมริกาและประเทศอื่นๆ อีกมากมายอัลกอริทึมแบบโลภ (greedy algorithm)ที่เลือกเหรียญที่มีมูลค่าสูงสุดซึ่งไม่เกินจำนวนเงินที่เหลืออยู่ที่จะผลิต จะให้ผลลัพธ์ที่ดีที่สุด อย่างไรก็ตาม นี่ไม่ใช่กรณีสำหรับระบบเหรียญกษาปณ์แบบสุ่ม หรือแม้แต่ระบบในโลกแห่งความเป็นจริงบางระบบ ตัวอย่างเช่น หากเราพิจารณาเหรียญกษาปณ์อินเดียแบบเก่า (ที่เลิกใช้แล้ว) ที่มีมูลค่า 5, 10, 20 และ 25 ไพเซ่ ในการผลิตเหรียญ 40 ไพเซ่ อัลกอริทึมแบบโลภจะเลือกเหรียญสามเหรียญ (25, 10, 5) ในขณะที่วิธีแก้ปัญหาที่ดีที่สุดคือการเลือกเหรียญสองเหรียญ (20, 20) อีกตัวอย่างหนึ่งคือการพยายามผลิตเหรียญ 40 เซนต์สหรัฐโดยไม่ใช้เหรียญนิกเกิล (มูลค่า 25, 10, 1) ซึ่งจะได้ผลลัพธ์ที่คล้ายกัน คือ อัลกอริทึมแบบโลภจะเลือกเหรียญเจ็ดเหรียญ (25, 10 และ 5 × 1) แต่ทางเลือกที่ดีที่สุดคือการเลือกเหรียญสี่เหรียญ (4 × 10) ระบบเหรียญเรียกว่า "แบบมาตรฐาน" หากอัลกอริทึมแบบโลภสามารถแก้ปัญหาการทอนเงินได้อย่างเหมาะสมเสมอ สามารถทดสอบได้ว่าระบบเหรียญเป็นแบบมาตรฐานหรือไม่ในเวลาพหุนาม^{[ 4 ]}

“ ปัญหา การกำหนดหน่วยเงิน ที่เหมาะสมที่สุด ” ^{[ 5 ]}เป็นปัญหาสำหรับผู้ที่ออกแบบสกุลเงินใหม่ทั้งหมด ปัญหานี้ถามว่าควรเลือกหน่วยเงินใดสำหรับเหรียญเพื่อลดต้นทุนเฉลี่ยในการทอนเงินให้น้อยที่สุด นั่นคือจำนวนเหรียญเฉลี่ยที่จำเป็นในการทอนเงิน เวอร์ชันของปัญหานี้ถือว่าผู้ที่ทอนเงินจะใช้จำนวนเหรียญขั้นต่ำ (จากหน่วยเงินที่มีอยู่) รูปแบบหนึ่งของปัญหานี้ถือว่าผู้ที่ทอนเงินจะใช้ “อัลกอริทึมแบบโลภ” ในการทอนเงิน แม้ว่าจะต้องใช้เหรียญมากกว่าจำนวนขั้นต่ำก็ตาม สกุลเงินปัจจุบันส่วนใหญ่ใช้ชุด 1-2-5แต่ชุดหน่วยเงินอื่น ๆ อาจต้องใช้หน่วยเงินน้อยกว่าหรือจำนวนเหรียญเฉลี่ยที่น้อยกว่าในการทอนเงิน หรือทั้งสองอย่าง

• รายการปัญหาของกระเป๋าเป้สะพายหลัง
• ปัญหาเหรียญ
• ปัญหาของนักสะสมเหรียญ

• M. Adamaszek, A. Niewiarowska (2010). "Combinatorics of the change-making problem". European Journal of Combinatorics . 31 (1): 47– 63. arXiv : 0801.0120 . doi : 10.1016/j.ejc.2009.05.002 . S2CID  13527488 .