คู่มือโอลิมปิกคอมพิวเตอร์

Greedy

หลักการ

• วิธีคิดสำหรับปัญหา optimization โดยทั่วไปแล้วจะมีขั้นตอน ซึ่งแต่ละขั้นจะมีตัวเลือกที่แตกต่างกันไป

• สำหรับหลายๆ ปัญหา optimization อาจจะไม่จำเป็นต้องใช้ dynamic programming เพื่อตัดสินตัวเลือกที่ดีที่สุด

• วิธีคิดแบบ greedy จะเลือกตัวเลือกที่ดีที่สุดในขณะนั้นๆ เสมอ โดยหวังว่าการเลือกตัวเลือกที่ดีที่สุดใน local จะนำไปสู่วิธีการแก้ปัญหาที่ดีที่สุดใน global

• วิธีคิดแบบ greedy จะไม่นำไปสู่วิธีการแก้ปัญหาที่ดีที่สุดเสมอไป มีเพียงบางปัญหาเท่านั้นที่สามารถนำไปใช้ได้

• การพิสูจน์ว่าสามารถใช้วิธีคิดแบบ greedy นั้นทำยาก บางครั้งการลองเขียนโค้ดไปเลยจะสะดวกกว่าการพิสูจน์

โจทย์ greedy ที่ดีมักมีคุณสมบัติว่าเมื่อตัดสินใจเลือกบางอย่างแล้ว เราไม่จำเป็นต้องย้อนกลับมาเปลี่ยนการเลือกนั้นอีก

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

พิจารณาปัญหาที่ต้องการทอนเงินมูลค่า n โดยใช้เหรียญที่มีมูลค่า {c₁, c₂, c…, c_k} จำนวนเหรียญที่น้อยที่สุดที่ต้องใช้เป็นเท่าไร?

ตัวอย่าง

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

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

และ n = 520

Greedy approach

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

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

ตัวอย่าง counterexample คือเหรียญ {1, 3, 4} และต้องทอน 6 ถ้าเลือกเหรียญใหญ่สุดก่อนจะได้ 4 + 1 + 1 ใช้ 3 เหรียญ แต่คำตอบที่ดีที่สุดคือ 3 + 3 ใช้ 2 เหรียญ

วิธีพิสูจน์ที่พบบ่อย

Exchange argument

สมมติว่ามีคำตอบที่ดีที่สุดอยู่แล้ว แล้วแสดงว่าสามารถสลับบางส่วนของคำตอบนั้นให้เหมือน greedy choice ได้โดยคำตอบไม่แย่ลง ถ้าทำซ้ำไปเรื่อย ๆ จะได้ว่ามี optimal solution ที่ตรงกับ greedy

Stay-ahead argument

เปรียบเทียบคำตอบของ greedy กับ optimal หลังจากตัดสินใจไปทีละขั้น แล้วพิสูจน์ว่า greedy ไม่เคยตามหลัง optimal เช่น เลือกงานได้ไม่น้อยกว่า หรือจบเร็วกว่าเสมอ

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

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

ตัวอย่าง

คำอธิบาย

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

ตัวอย่าง implementation

vector<pair<int, int>> job; // {end, start}
sort(job.begin(), job.end());

int last_end = -1;
int ans = 0;

for (auto [end, start] : job) {
  if (start >= last_end) {
    ans++;
    last_end = end;
  }
}

โจทย์ที่มักใช้ greedy

• interval scheduling: เลือกงานที่จบเร็วสุด

• minimum number of rooms: ใช้ sweep line หรือ priority queue

• Huffman coding: รวมค่าน้อยสุดสองตัวเสมอ

• minimum spanning tree: Kruskal และ Prim เป็น greedy

• Dijkstra: เลือก node ที่ distance น้อยสุดที่ยังไม่ finalize

Checklist

• ระบุ objective ว่าต้อง maximize หรือ minimize อะไร

• เขียน greedy choice ให้ชัดเจน เช่น “เลือกงานที่จบเร็วสุด”

• หา counterexample ถ้ามี เพื่อไม่ใช้ greedy ผิดโจทย์

• ถ้าต้องพิสูจน์ ให้ลอง exchange argument ก่อน