الگوریتم‌های حریصانه پیشرفته
حریصانه پیشرفته: زمان‌بندی با فاصله، مسئله پرش و کد هافمن (مفهومی) — کجا حریصی اثبات‌شده جواب می‌دهد
حریصانه فراتر از پایه
در دوره DSA، حریصانه پایه را دیدید. اینجا سه مسئله پیشرفته‌تر که حریصی آن‌ها اثبات‌شده است:
۱. زمان‌بندی با فاصله (Task Scheduler)
وظایف با خنکی n: بین دو وظیفه یکسان، حداقل n واحد فاصله. کمترین زمان کل؟
بینش حریصانه: پرتکرارترین اول — فریم (max_count−1)×(n+1)+1 بساز و بقیه را در شکاف‌ها بچین!
۲. مسئله پرش (Jump Game)
آرایه‌ای که arr[i] = حداکثر پرش از i. به آخر می‌رسیم؟
حریصانه از راست: «آخرین خوب» را نگه دار؛ اگر i + arr[i] ≥ آخرین‌خوب ← i خوب است. O(n)!
last_good = n - 1
for i from n-2 downto 0:
if i + arr[i] >= last_good:
last_good = i
return last_good == 0۳. کد هافمن (مفهومی)
فشرده‌سازی بهینه: کاراکتر پرتکرار = کد کوتاه! حریصانه: دو گره کم‌فراوانی را با هیپ ادغام کن — درخت بهینه prefix-free. پایه ZIP و JPEG!
حریصانه یا DP؟
| معیار | حریصانه | DP |
|---|---|---|
| انتخاب محلی | قطعی و نهایی | همه گزینه‌ها امتحان |
| سرعت | سریع ✓ | کندتر |
| تضمین بهینه | فقط با اثبات! | همیشه ✓ |
| مثال شکست حریصی | سکههای [1,3,4] هدف ۶: حریصی 4+1+1=3، بهینه 3+3=2! | — |
هشدار: قبل از حریصانه، با مثال نقض چالش کنید! اگر شک دارید، DP امن‌تر است. حریصانه اثبات‌نشده = جواب احتمالاً غلط.
جمع‌بندی
- زمان‌بندی: پرتکرار اول + فریم
- Jump: آخرین‌خوب از راست — O(n)
- هافمن: هیپ + ادغام کم‌فراوان‌ها
- همیشه مثال نقض بسازید قبل از اعتماد
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.