แนวคิดหลัก (Concept)
Greedy Choice Property: คือการตัดสินใจเลือกทางเลือกที่ "ดีที่สุดในขณะนั้น" (Local Optimal) โดยเชื่อว่าการเลือกที่ดีที่สุดในทุกๆ ก้าว จะนำไปสู่ผลลัพธ์ที่ดีที่สุดในตอนจบ
"เหมือนคนเดินขึ้นเขาที่เลือกก้าวเท้าไปทางที่ชันที่สุดเสมอ เพราะคิดว่าจะถึงยอดเขาเร็วที่สุด"
3 ขั้นตอนการทำงาน (The 3 Steps)
Selection
เลือกชิ้นที่ดีที่สุด ณ ตอนนั้น (จากข้อมูลที่ Sort แล้ว)
Feasibility Check
เช็คเงื่อนไขว่า "เอามาแล้วไม่พังใช่ไหม" (เช่น เงินทอนพอไหม)
Solution Update
ถ้าเงื่อนไขผ่าน ให้เก็บเข้ากระเป๋า แล้วทำซ้ำจนจบ
Workshop 1: เครื่องทอนเงิน
หลักการ: "หยิบเหรียญที่ใหญ่ที่สุด เท่าที่จะหยิบได้ก่อน"
Log การทำงาน:
- รอรับคำสั่ง...
ถาดรับเงินทอน
ข้อควรระวัง (The Trap)
Greedy ไม่ได้ให้คำตอบที่ดีที่สุดเสมอไป! ลองดูตัวอย่างเหรียญบน "ดาวอังคาร"
โจทย์: ทอนเงิน 6 บาท
เหรียญที่มีบนดาวอังคาร: [4, 3, 1]
กดปุ่มเพื่อทดสอบผลลัพธ์
Workshop 2: นักช้อปงบน้อย
เป้าหมาย: ซื้อของให้ได้ "จำนวนชิ้น" เยอะที่สุด ภายใต้งบประมาณที่มี (เรียงจากถูกไปแพง)
ชั้นวางสินค้า
Sorted: Low to Highตะกร้าสินค้า
ยังไม่มีสินค้า