แผนการเรียน
/

Greedy & Divide and Conquer
Optimization Techniques

Day 09 Afternoon: กลยุทธ์การเลือกสิ่งที่คุ้มค่าที่สุดและการแบ่งส่วนปัญหาเพื่อหาคำตอบที่เหมาะสม

หัวข้อที่จะเรียนรู้

1
แนวคิด Greedy Algorithms และการพิสูจน์ความถูกต้อง
2
Divide and Conquer สำหรับการแก้ปัญหา Optimization
3
เทคนิค Binary Search on Answer สำหรับการหาค่าที่เหมาะสมที่สุด

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Greedy: การเลือกโหนดที่ "ดีที่สุด" ในขณะนั้น

  • Local Optimality: สร้างคำตอบโดยการเลือกสิ่งที่ดูดีที่สุดในปัจจุบันเสมอ
  • Irrevocability: เมื่อเลือกไปแล้วจะไม่มีการย้อนกลับไปแก้ไขสิ่งที่เลือก
  • Efficiency: มักจะเป็นอัลกอริทึมที่มีความเร็วสูงมากเมื่อเทียบกับ DP
  • Challenge: ความยากอยู่ที่การหา "Greedy Strategy" ที่รับประกันว่าจะได้คำตอบที่ดีที่สุดระดับ Global

แหล่งอ้างอิง: https://www.geeksforgeeks.org/greedy-algorithms/

ปัญหาการทอนเงิน (Coin Problem)

โจทย์: ต้องการทอนเงินจำนวน ( n ) ด้วยจำนวนเหรียญที่น้อยที่สุด

  • Greedy Strategy: เลือกเหรียญที่มีค่ามากที่สุดที่ไม่เกินจำนวนเงินที่เหลือ
  • ตัวอย่าง: เงินยูโร {1, 2, 5, 10, 20, 50, 100, 200} สำหรับยอด 520: ( 200 + 200 + 100 + 20 ) = 4 เหรียญ (Optimal)
  • ข้อควรระวัง: หากค่าเหรียญเป็น {1, 3, 4} และต้องการทอน 6: Greedy จะเลือก ( 4 + 1 + 1 ) = 3 เหรียญ แต่คำตอบจริงคือ ( 3 + 3 ) = 2 เหรียญ

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Scheduling Strategy

โจทย์: มีกิจกรรมที่มีเวลาเริ่มและสิ้นสุด ต้องการเลือกจำนวนกิจกรรมที่มากที่สุดโดยไม่ซ้อนทับกัน

เลือกกิจกรรมที่สั้นที่สุด (Incorrect)
เลือกกิจกรรมที่เริ่มก่อน (Incorrect)
Optimal Strategy: เลือกกิจกรรมที่ สิ้นสุดเร็วที่สุด (Ends Early) เสมอเพื่อให้เหลือเวลาสำหรับกิจกรรมถัดไปมากที่สุด

แหล่งอ้างอิง: https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/

ภารกิจและกำหนดส่ง (Tasks & Deadlines)

โจทย์: ได้คะแนน ( d - f ) โดย ( d ) คือเดดไลน์ และ ( f ) คือเวลาที่ทำเสร็จจริง

  • น่าประหลาดใจที่ Optimal Strategy ไม่ขึ้นกับเดดไลน์เลย!
  • กลยุทธ์ที่ถูกต้องคือ: ทำภารกิจที่ใช้เวลาน้อยที่สุดก่อน (Shortest Task First)
  • การสลับงานที่ใช้เวลามากกว่ามาทำก่อน จะทำให้คะแนนรวมลดลงอย่างแน่นอนเสมอ

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Divide and Conquer Concept

1. Divide

แบ่งปัญหาใหญ่เป็นปัญหาย่อยที่ เป็นอิสระต่อกัน

2. Conquer

แก้ปัญหาย่อยโดยใช้การเรียกซ้ำ (Recursion)

3. Combine

รวมคำตอบจากปัญหาย่อยเข้าด้วยกันเป็นคำตอบเดียว

ตัวอย่างเช่น: Merge Sort, Quick Sort, Binary Search

แหล่งอ้างอิง: https://www.geeksforgeeks.org/divide-and-conquer/

Binary Search on Answer

ใช้เมื่อการคำนวณหาคำตอบโดยตรงนั้นยาก แต่การ ตรวจสอบ (Check) ว่าค่าที่กำหนดให้นั้นเป็นไปได้หรือไม่นั้นทำได้ง่าย:

  • ต้องการหาค่า ( x ) ที่เหมาะสมที่สุด
  • ฟังก์ชันความถูกต้อง ( ok(x) ) ต้องมีความเป็น Monotonic (เช่น ถ้า x เป็นไปได้ ค่าที่มากกว่า x ทั้งหมดก็ต้องเป็นไปได้)
  • ใช้เวลา ( O(f(n) \log Z) ) โดย ( f(n) ) คือเวลาที่ใช้ในการเช็ค และ ( Z ) คือช่วงของคำตอบ

แหล่งอ้างอิง: https://usaco.guide/general/binary-search

Finding the Maximum Value

ใช้ Binary Search หาจุดสูงสุดของฟังก์ชันที่เพิ่มขึ้นแล้วลดลง:

int x = -1;
for (int b = z; b >= 1; b /= 2) {
  while (!ok(x+b)) x += b;
}
int k = x+1;

แนวคิดนี้ช่วยเปลี่ยนปัญหาการค้นหาเชิงเส้น ( O(n) ) ให้กลายเป็น ( O(\log n) ) โดยอาศัยสมบัติของฟังก์ชัน

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Optimization: Cutting Hot Dogs

โจทย์: มีเส้นวัตถุดิบความยาวต่างๆ ต้องการตัดให้ได้ ( M ) ชิ้นที่ความยาวเท่ากัน ( x ) จงหา ( x ) ที่มากที่สุด

  • Check Function: ให้ความยาว ( x ) มา เราสามารถคำนวณจำนวนชิ้นที่ได้ใน ( O(n) ) ด้วยการหาร ( \lfloor L_i / x \rfloor )
  • จำนวนชิ้นที่ได้จะแปรผกผันกับค่า ( x ) (ยิ่งตัดยาว ชิ้นยิ่งน้อย)
  • ใช้ Binary Search สุ่มค่า ( x ) ในช่วง ( [0, 10^9] ) จนกว่าจะได้ความแม่นยำที่ต้องการ

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Precision in Binary Search

เมื่อทำงานกับเลขทศนิยม (Floating point):

  • ปัญหา: การใช้ `while (hi - lo > eps)` อาจเกิด Infinite Loop จากข้อจำกัดของ Precision
  • ทางออก: ใช้การวนลูปแบบคงที่ (Fixed Iterations) เช่น 100 รอบ
  • การรัน 100 รอบจะลดช่วงค้นหาลงเหลือเพียง ( 1 / 2^{100} ) ซึ่งแม่นยำเกินพอสำหรับโจทย์ส่วนใหญ่
  • ( 2^{100} ) มีค่าประมาณ ( 10^{30} ) ซึ่งเล็กกว่าหน่วยที่เล็กที่สุดของ `double`

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

เงื่อนไขสำคัญ: Monotonicity

การจะใช้ Binary Search on Answer ได้ ฟังก์ชันการตรวจสอบ ( (ok(x)) ) ต้องมีสมบัติเปลี่ยนผ่านเพียงครั้งเดียว:

x: 0, 1, 2, ..., k-1, k, k+1, ...
ok(x): false, false, ..., false, true, true, ...
  • เราต้องการหาค่า ( k ) ซึ่งเป็นค่าที่น้อยที่สุดที่ทำให้เงื่อนไขเป็นจริง
  • หากฟังก์ชันมีลักษณะขึ้นๆ ลงๆ (ไม่เป็น Monotonic) จะไม่สามารถใช้วิธีนี้ได้
  • ช่วงการค้นหา ( [L, R] ) ต้องครอบคลุมคำตอบที่เป็นไปได้ทั้งหมด

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

ตัวอย่าง: การตัดวัตถุดิบ (CountRods)

ฟังก์ชันตรวจสอบความถูกต้อง:

int countRods(vector<int> A, double x) {
  int dogs = 0;
  for (int l : A) dogs += (int)(l / x);
  return dogs;
}

ในโจทย์นี้ ( countRods ) จะมีค่าลดลงเมื่อ ( x ) เพิ่มขึ้น (Monotonically Decreasing) เราจึงสามารถใช้ Binary Search เพื่อหาค่า ( x ) ที่มากที่สุดที่ยังทำให้ได้จำนวนชิ้น ( \ge M ) ตามต้องการได้

แหล่งอ้างอิง: https://github.com/usaco-guide/usaco-guide

Merge Sort และการแบ่งส่วนปัญหา

  • Divide: แบ่งอาเรย์ออกเป็น 2 ส่วนเท่าๆ กันจนเหลือขนาด 1
  • Conquer: สลับตำแหน่งเพื่อเรียงลำดับในส่วนย่อย
  • Combine: รวม 2 ส่วนที่เรียงแล้วเข้าด้วยกันโดยใช้เวลา ( O(n) )
  • ความซับซ้อนรวม ( O(n \log n) ) เป็นมาตรฐานที่ใช้เปรียบเทียบกับวิธี Optimization อื่นๆ

แหล่งอ้างอิง: https://www.geeksforgeeks.org/merge-sort/

Meet in the Middle Optimization

ใช้ลดความซับซ้อนของปัญหาประเภท Exponential เช่น ( O(2^n) ) ให้เหลือ ( O(2^{n/2}) ):

  • แบ่งข้อมูลออกเป็น 2 ส่วนขนาดเท่ากัน ( (n/2) )
  • ทำ Brute Force แยกกันทั้ง 2 ส่วนเพื่อหาผลลัพธ์ที่เป็นไปได้ทั้งหมด
  • ใช้การค้นหา (เช่น Binary Search หรือ Hash Map) เพื่อรวมผลลัพธ์จากทั้งสองฝั่ง
  • ถูกนำเสนอครั้งแรกในปี 1974 โดย E. Horowitz และ S. Sahni

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Optimization: Subset Sum ( (n=40) )

โจทย์: หาเซตย่อยที่บวกกันได้ ( T ) จากเลข 40 ตัว

  • ( 2^{40} ) มีค่าประมาณ ( 10^{12} ) ซึ่งใช้เวลานานเกินไป
  • แบ่งเป็น 2 ฝั่ง ฝั่งละ 20 ตัว: ( 2^{20} ) มีค่าเพียง ( 10^6 )
  • สร้างรายการผลรวม ( SA ) และ ( SB ) จากทั้ง 2 ฝั่ง
  • หา ( x \in SA ) และ ( y \in SB ) ที่ ( x + y = T ) โดยใช้ Binary Search ในเวลา ( O(2^{n/2} \cdot n) )

แหล่งอ้างอิง: https://www.geeksforgeeks.org/meet-in-the-middle/

Activity Selection Problem

ต้องการเลือกกิจกรรมที่ไม่ซ้อนทับกันให้ได้จำนวนมากที่สุด:

Algorithm: เรียงกิจกรรมตามเวลา สิ้นสุด (Finish Time) และเลือกกิจกรรมถัดไปที่เริ่มหลังงานก่อนหน้าจบ

ความซับซ้อนคือ ( O(n \log n) ) จากการเรียงลำดับข้อมูล ซึ่งเร็วกว่าการใช้ DP ในโจทย์ประเภทนี้มาก

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Proving Greedy: Exchange Argument

เราจะมั่นใจได้อย่างไรว่า Greedy ของเราให้คำตอบที่ดีที่สุด (Optimal)?

  • Exchange Argument: สมมติว่ามีคำตอบอื่นที่ Optimal กว่า Greedy ของเรา
  • ลองทำการ "สลับสมาชิก" ในคำตอบนั้นด้วยสมาชิกจาก Greedy Strategy ของเรา
  • พิสูจน์ว่าหลังการสลับ คำตอบนั้นยังคง Optimal อยู่ หรือดีขึ้นกว่าเดิม
  • หากสลับได้เรื่อยๆ จนกลายเป็น Greedy Solution แสดงว่า Greedy ของเราคือ Optimal

แหล่งอ้างอิง: https://en.wikipedia.org/wiki/Greedy_algorithm

Greedy vs. DP

หัวข้อ Greedy Dynamic Programming
การเลือก เลือกสิ่งที่ดีที่สุด ณ ตอนนี้ทันที ลองทุกทางเลือกที่เป็นไปได้
ความซับซ้อน มักจะต่ำมาก ( (O(n)) หรือ (O(n \log n)) ) สูงกว่า (ขึ้นกับจำนวน State)
ความถูกต้อง ต้องพิสูจน์ด้วยความยากลำบาก รับประกันโดยธรรมชาติของการลองทุก State

แหล่งอ้างอิง: https://www.geeksforgeeks.org/greedy-approach-vs-dynamic-programming/

เตรียมตัวเข้าสู่ช่วงปฏิบัติ

15:00 - 17:00 น. ตะลุยโจทย์ Range Queries และ Optimization:

  • การ Implement Segment Tree สำหรับโจทย์ Range Minimum Query (RMQ)
  • การใช้ Fenwick Tree แก้ปัญหาเลขลำดับที่หายไป
  • การทำ Binary Search on Answer ร่วมกับ Greedy เช็คความเป็นไปได้
  • ฝึกแก้โจทย์จากระบบ Grader (IOI Style)

"ความรู้ทางทฤษฎีจะไร้ผล หากไม่ผ่านการเขียนโค้ดจริง"

Optimization Session Wrap-up

หัวใจสำคัญที่เราได้รับในวันนี้:

Greedy Choice Property
Monotonic Searching
Search Space Reduction
D&C Strategy

"ถึงเวลาพักสมองสั้นๆ ก่อนเข้าสู่ช่วงลงมือทำจริงในลำดับถัดไป!"

15:00 น. เริ่มช่วง Practice