Tossaporn Saengja

Greedy

หลักการ

ปัญหาการทอนเหรียญ

พิจารณาปัญหาที่ต้องการทอนเงินมูลค่า n โดยใช้เหรียญที่มีมูลค่า {c1,c2,⋯ ,ck}\{c_1, c_2, \cdots, c_k\} จำนวนเหรียญที่น้อยที่สุดที่ต้องใช้เป็นเท่าไร?

ตัวอย่าง

มูลค่าของเหรียญคือ

{1,2,5,10,20,50,100,200}\{1,2,5,10,20,50,100,200\}

และ n = 520

Greedy approach

ตัวอย่างวิธีคิดแบบ greedy คือเลือกเหรียญที่มีมูลค่ามากสุดก่อนเสมอ จนกว่าเราจะสามารถรวมมูลค่าได้ถูกต้อง

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

ปัญหาการจัดตารางเวลา

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

ตัวอย่าง

งาน เวลาเริ่ม เวลาจบ
A 1 3
B 2 5
C 3 9
D 6 8

คำอธิบาย

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

เพิ่มเติม