สมมุติว่าเรามีเหรียญขนาดดังต่อไปนี้
เหรียญ 10 บาท, เหรียญ 5 บาท, และเหรียญ 1 บาท
และสมมุติว่าเราต้องการแลกเงิน 89 บาท เราจะได้เงินเหรียญดังนี้
เหรียญ 10 บาท จะได้ 8 เหรียญ
เหรียญ 5 บาท จะได้ 1เหรียญ
เหรียญ 1 บาท จะได้ 4 เหรียญ
จะเห็นว่าอัลกอริทึมที่เราใช้ก็คือ เราเลือกเหรียญที่มีค่ามากที่สุด แต่ไม่มากกว่า 89 บาท ออกมาก่อน (เหรียญ 10 บาท ได้ 8 เหรียญ = 80 บาท) จากนั้นลบค่านี้ออกจาก 89 บาท ก็จะเหลือ 9 บาท หลังจากนั้นเราเลือกเหรียญที่มีค่ามากที่สุดแต่ไม่เกิน 9 บาท นั่นก็คือได้เหรียญ 5 บาทอีก 1 เหรียญ แล้วลบค่านี้ออกจาก 9 บาท จะเหลืออยู่อีก 4 บาท และในที่สุดเราก็จะได้เหรียญ 1 บาทอีก 4 เหรียญ
วิธีการนี้เราอาจเรียกได้ว่า "Greedy Algorithm"
อัลกอริทึมนี้มีหลักการอยู่ว่า ในขณะใดๆก็ตาม เราจะหาคำตอบที่ดีที่สุดของปัญหา โดยการเลือกเอาคำตอบที่ดีที่สุด ในสถานะนั้นออกมาก่อน โปรดสังเกตว่าปัญหาของการแลกเหรียญที่กล่าวมาข้างต้น จะใช้ได้ดีกับอัลกอริทึมนี้ เนื่องจากคุณสมบัติพิเศษ ของเหรียญนั่นเอง ทีนี้ลองมาดูตัวอย่างใหม่ จะทำให้เห็นอะไรได้ชัดเจนมากยิ่งขึ้น
สมมุติว่าเรามีเหรียญขนาดดังต่อไปนี้
เหรียญ 11 บาท, เหรียญ 5 บาท, และเหรียญ 1 บาท
และสมมุติว่าเราต้องการแลกเงิน 15 บาท ถ้าเราใช้ Greedy Algorithm เราจะได้เงินเหรียญดังนี้คือ
เหรียญ 11 บาท จะได้ 1 เหรียญ
เหรียญ 1 บาท จะได้ 4 เหรียญ
รวมทั้งหมดแล้วจะได้เหรียญทั้งหมด 5 เหรียญ จะเห็นได้ว่าคำตอบนี้ไม่ใช่คำตอบที่ดีที่สุด เนื่องจากคำตอบที่แท้จริง
*** ควรจะต้องได้เหรียญ 5 บาท ทั้งหมด 3 เหรียญเท่านั้น ***
อย่างไรก็ตามขอย้ำไว้อีกครั้งหนึ่งว่าวิธีการแบบ Greedy Algorithm นี้ไม่ได้ให้คำตอบที่ดีที่สุดออกมา แต่สำหรับวิธีการนี้ก็ค่อนข้างจัดได้ว่าจะให้คำตอบที่จัดว่า ดี ออกมาได้ (ต้องพิจารณาแต่ละกรณี)
*** หากไปทดสอบเขียนเป็นโปรแกรม ต้องใช้วิธีการหารเอาเศษเข้ามาช่วยด้วยน่ะครับ ***
| 
