Greedy
หลักการ
ปัญหา optimization หลายข้อแก้ได้โดยตัดสินใจทีละขั้น Greedy คือการเลือกตัวเลือกที่ดูดีที่สุด ณ ตอนนั้น เสมอ โดยไม่ย้อนกลับมาเปลี่ยน และหวังว่าการเลือกที่ดีที่สุดเฉพาะหน้า (local) จะนำไปสู่คำตอบที่ดีที่สุดโดยรวม (global)
ข้อดี: คิดง่าย เขียนสั้น และมักเร็ว (ส่วนใหญ่คือ sort แล้ววนหนึ่งรอบ O\left( n\log n \right))
ข้อเสีย: ไม่ได้ถูกเสมอไป greedy ที่ดูสมเหตุสมผลหลายแบบให้คำตอบผิด จึงต้องมีเหตุผลหรือพิสูจน์ว่ากฎที่เลือกถูกต้อง
ปัญหาการทอนเหรียญ
ต้องการทอนเงิน n บาทด้วยเหรียญมูลค่า c_{1},c_{2},\cdots,c_{k} ให้ใช้จำนวนเหรียญน้อยที่สุด
กฎ greedy: หยิบเหรียญมูลค่ามากที่สุดที่ยังไม่เกินจำนวนที่เหลือ ทำซ้ำจนครบ
เช่น เหรียญ \{ 1,2,5,10,20,50,100,200\} และ n = 520: หยิบ 200 + 200 + 100 + 20 ได้ 4 เหรียญ ซึ่งดีที่สุด
แต่ถ้าเหรียญเป็น \{ 1,3,4\} และ n = 6 greedy ได้ 4 + 1 + 1 (3 เหรียญ) ขณะที่คำตอบจริงคือ 3 + 3 (2 เหรียญ) greedy ใช้ได้กับชุดเหรียญบางแบบเท่านั้น กรณีทั่วไปต้องใช้ Dynamic Programming (ดูบท Dynamic Programming ซึ่งมี widget เปรียบเทียบทั้งสองวิธี)
ปัญหาการจัดตารางเวลา (interval scheduling)
มีงาน n งาน แต่ละงานมีเวลาเริ่มและเวลาจบ ทำได้ทีละงาน ต้องการเลือกงานที่ไม่ชนกันให้ได้ จำนวนมากที่สุด
| งาน | เวลาเริ่ม | เวลาจบ |
|---|---|---|
| A | 1 | 3 |
| B | 2 | 5 |
| C | 3 | 9 |
| D | 6 | 8 |
มี greedy ที่น่าลองหลายแบบ
เลือกงานที่ เริ่มเร็วสุด ก่อน
เลือกงานที่ สั้นสุด ก่อน
เลือกงานที่ จบเร็วสุด ก่อน
ลองแต่ละกฎกับชุดงานต่าง ๆ แล้วดูว่ากฎไหนได้คำตอบดีที่สุดทุกครั้ง
มีเพียง จบเร็วสุดก่อน ที่ถูกเสมอ ตัวอย่างในตารางได้คำตอบ 2 งาน คือ A และ D
vector<pair<int, int>> job; // {end, start} เพื่อให้ sort ตามเวลาจบ
sort(job.begin(), job.end());
int lastEnd = INT_MIN, count = 0;
for (auto [end, start] : job) {
if (start >= lastEnd) { // ไม่ชนกับงานล่าสุดที่เลือก
count++;
lastEnd = end;
}
}พิสูจน์ว่า greedy ถูก
Exchange argument
สมมติว่ามีคำตอบที่ดีที่สุด (optimal) อยู่แล้ว แล้วแสดงว่า สลับ บางส่วนให้เหมือน greedy ได้โดยคำตอบไม่แย่ลง ทำซ้ำไปเรื่อย ๆ จนได้คำตอบที่ตรงกับ greedy และยังดีที่สุด
ตัวอย่างกับ interval scheduling: ให้ g เป็นงานที่จบเร็วที่สุด และ o เป็นงานแรกในคำตอบ optimal เพราะ g จบไม่ช้ากว่า o การเปลี่ยน o เป็น g จึงไม่ทำให้ชนกับงานถัดไปในคำตอบ จำนวนงานเท่าเดิม ดังนั้นมีคำตอบ optimal ที่เริ่มด้วย g เสมอ แล้วใช้เหตุผลเดิมกับงานที่เหลือต่อไปได้
Stay-ahead argument
เทียบ greedy กับ optimal หลังตัดสินใจทีละขั้น แล้วพิสูจน์ว่า greedy ไม่เคยตามหลัง เช่น หลังเลือกงานไป k งาน งานที่ k ของ greedy จบไม่ช้ากว่างานที่ k ของ optimal เสมอ
หา counterexample ก่อนเสมอ
ก่อนเขียนโค้ด ให้ลองหาตัวอย่างเล็ก ๆ ที่กฎผิด (เหมือนที่ widget แสดง) ถ้าหาไม่เจอหลังลองหลายแบบ ค่อยพยายามพิสูจน์ หรือเขียน brute force มาเทียบผลกับ input สุ่ม (stress test)
Greedy ที่พบบ่อยอีกสองแบบ
จับคู่ด้วยสองตัวชี้ (two pointers)
โจทย์ Ferris Wheel: กระเช้าหนึ่งตัวรับได้ไม่เกิน 2 คนและน้ำหนักรวมไม่เกิน x ใช้กระเช้าน้อยที่สุดกี่ตัว Sort น้ำหนักแล้วพยายามจับคนที่เบาที่สุดคู่กับคนที่หนักที่สุด ถ้าเกิน คนที่หนักที่สุดต้องนั่งคนเดียว
sort(w.begin(), w.end());
int i = 0, j = n - 1, gondolas = 0;
while (i <= j) {
if (i < j && w[i] + w[j] <= x) i++; // คนเบาสุดนั่งไปกับคนหนักสุด
j--; // คนหนักสุดได้กระเช้าแล้ว
gondolas++;
}เรียงตามเวลาที่ใช้
โจทย์ Tasks and Deadlines: ทำงานทีละงาน งานที่ i ใช้เวลา a_{i} และได้คะแนน d_{i} - f_{i} เมื่อ f_{i} คือเวลาที่ทำเสร็จ คะแนนรวมคือ \sum d_{i} - \sum f_{i} ส่วนแรกคงที่ จึงต้องทำให้ \sum f_{i} น้อยสุด ซึ่งได้จากการ ทำงานที่สั้นกว่าก่อน (exchange argument: ถ้างานยาวอยู่หน้างานสั้น สลับกันแล้ว \sum f_{i} ลดลง)
โจทย์ที่มักใช้ greedy
Interval scheduling: เลือกงานที่จบเร็วสุด
จำนวนห้องน้อยสุดสำหรับทุกงาน: sweep line หรือ priority queue
Huffman coding: รวมสองค่าที่น้อยที่สุดเสมอ
Minimum spanning tree: Kruskal และ Prim (บท Graph Algorithm)
Dijkstra: เลือก node ที่ระยะน้อยสุดที่ยังไม่ยืนยัน
Checklist
ระบุให้ชัดว่าต้อง maximize หรือ minimize อะไร
เขียนกฎ greedy เป็นประโยคเดียว เช่น “เลือกงานที่จบเร็วสุด”
ลองหา counterexample ด้วยตัวอย่างเล็ก ๆ
ถ้าต้องพิสูจน์ ลอง exchange argument ก่อน
โจทย์ฝึกฝน (Practice Problems)
ลองทำโจทย์เหล่านี้จาก CSES Problem Set เพื่อฝึกใช้ทักษะจากบทนี้ โดยเริ่มจากโจทย์ที่ง่ายที่สุดก่อน
Movie Festival (interval scheduling)
โจทย์เพิ่มเติม: CSES Problem Set และ programming.in.th