บทที่ 23 greedy
จบบทนี้ น้องจะแก้โจทย์แบบ "เลือกให้ได้มากที่สุด" "จัดลำดับให้รอน้อยที่สุด" หรือ "รวมของให้ต้นทุนต่ำที่สุด" ด้วยการเลือกสิ่งที่ดีที่สุดตอนนี้ทีละขั้น ซึ่งส่วนใหญ่เป็นแค่การเรียงข้อมูลให้ถูกค่าแล้วไล่ครั้งเดียวในเวลา O(N log N) หรือใช้ priority_queue เมื่อตัวที่ดีที่สุดเปลี่ยนไปเรื่อยๆ ที่สำคัญกว่าการเขียนคือการรู้ว่า greedy ถูกเมื่อไร บทนี้สอนเหตุผลแบบแลกเปลี่ยนที่ใช้พิสูจน์ได้เกือบทุกข้อ ชี้โจทย์ที่ greedy ผิดแบบที่ต้องรอ dynamic programming ในบทที่ 24 และ 25 และสอน stress test ที่จับ greedy ผิดได้ก่อนส่ง โจทย์แนวนี้ออกในค่าย 2 และ TOI แทบทุกปี เพราะโค้ดสั้นแต่คิดผิดได้ง่าย
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 23.1 คิดแบบ greedy และทอนเหรียญ | ทอนเหรียญ 1 2 5 10 ที่ greedy ถูกและพิสูจน์ได้ เหรียญ 1 3 4 ที่ greedy ผิด และโปรแกรมตรวจด้วย brute force |
| 23.2 เลือกกิจกรรมที่ไม่ซ้อนกัน | กฎที่ฟังดูดีสามแบบ ทำไมต้องเรียงตามเวลาจบ และการพิสูจน์แบบแลกเปลี่ยนทีละขั้น |
| 23.3 เรียงงาน เส้นตาย และ knapsack แบบแบ่งได้ | เวลารอรวมน้อยสุด ค่าสายมากสุดน้อยสุด เรียงตามราคาต่อหน่วยด้วยการคูณไขว้ และ 0/1 knapsack ที่ greedy ผิด |
| 23.4 greedy กับ priority_queue | รวมเชือกให้ต้นทุนน้อยสุดแบบ Huffman และเลือกงานค่าจ้างสูงสุดก่อนเส้นตายด้วยการคืนงานที่ถูกที่สุด |
| 23.5 ตรวจ greedy ด้วย stress test | สี่ส่วนของ stress test ในไฟล์เดียว เจอตัวอย่างที่ greedy ผิดภายในชุดแรก และกับดักของ brute force ที่ผิดตาม |