หาจำนวนธนบัตรน้อยที่สุดสำหรับจำนวนเงิน (Greedy Algorithm) - JavaScript

ปัญหาการหาจำนวนธนบัตร/เหรียญน้อยที่สุด (Minimum Notes/Coins) โดยใช้ Greedy Algorithm เลือกมูลค่าสูงสุดก่อนเสมอ

มูลค่าเงิน (Denominations)

1000, 500, 100, 50, 20, 10, 5, 2, 1

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

const sum = 512;

const countNotes = sum => {
  let count = 0;
  const denominations = [1000, 500, 100, 50, 20, 10, 5, 2, 1];
  
  for (const denom of denominations) {
    count += Math.floor(sum / denom);
    sum %= denom;
  }
  return count;
};

console.log(countNotes(sum));

ผลลัพธ์

3

คำอธิบาย

512 = 500 × 1 + 10 × 1 + 2 × 1 = 3 ใบ/เหรียญ

ข้อจำกัดของ Greedy

Greedy ให้คำตอบที่เหมาะสม (optimal) ก็ต่อเมื่อระบบมูลค่าเป็น canonical coin system (เช่น เงินไทย, สกุลเงินส่วนใหญ่) หากมูลค่าเป็น [1, 3, 4] และต้องการ 6 → Greedy ให้ 4+1+1 (3 เหรียญ) แต่ optimal คือ 3+3 (2 เหรียญ) ต้องใช้ Dynamic Programming แทน