در زمان‌بندیِ وزنیِ بازه‌ها،شروع،پایان و ارزش هر کار از قبل معلوم است. می‌خواهیم زیرمجموعه‌ای بدون هم‌پوشانی با بیشترین مجموع ارزش انتخاب کنیم. روشِ «هرچه زودتر تمام می‌شود بردار» برای نسخهٔ وزنی لزوماً جوابِ بهینه نمی‌دهد؛ این تمرین با predecessor و برنامه‌ریزی پویا،هم ارزش و هم خودِ انتخاب‌ها را بازسازی می‌کند.
سه بازه که روش حریصانه را شکست می‌دهند
| بازه | زمانِ نیمه‌باز | ارزش |
|---|---|---|
| A | [۰،۳) | ۵ |
| B | [۳،۵) | ۵ |
| C | [۰،۵) | ۱۱ |
انتخاب بر اساس پایانِ زودتر،A و سپس B را می‌گیرد؛ مجموع ارزش۱۰ است. انتخابِ C به‌تنهایی ارزش۱۱ دارد. تمام عددها اصیل و آموزشی‌اند؛ قیمت خدمات،نوبت مشتری یا برنامهٔ واقعیِ کارکنان نیستند. ارزشِ بیشترِ C را از طولِ زمانش حدس نمی‌زنیم؛ آن یک ورودیِ جداست.
قرارداد [start,end) یعنی نقطهٔ پایان بیرونِ بازه است. پس A وB در مرز۳ با هم تعارض ندارند. اگر این مرز را بسته فرض کنیم،مسئله و مجموعهٔ جواب‌های مجاز عوض می‌شود؛ کد و oracle هر دو قرارداد نیمه‌باز را صریح دارند.
p(j) کدام گذشته را نگه می‌دارد؟
بازه‌ها با پایان،سپس شروع و سپس شناسه مرتب می‌شوند. p(j) آخرین بازهٔ قبلی است که پایانش از شروعِ j بیشتر نیست. بنابراین اگر j را انتخاب کنیم،فقط جوابِ بخشِ قبل تا آن مرز را می‌توانیم به ارزشش اضافه کنیم. یک «بهترین جوابِ کل گذشته» بدون شناخت این مرز ممکن است بازهٔ ناسازگار را هم بردارد.
در کد،خانهٔ صفر DP مجموعهٔ خالی است و p به شمارهٔ خانهٔ جدول اشاره می‌کند. برای هر بازه،دو مقدار مستقل داریم: exclude یعنی بهترین جواب بدون بازهٔ جاری،و include یعنی ارزشِ جاری به‌علاوهٔ DP در مرزِ سازگار. خانهٔ تازه،بیشترِ این دو است.
از ارزش به نامِ بازه‌ها برگردیم
از آخر جدول عقب می‌رویم. اگر شاخهٔ include واقعاً بزرگ‌تر باشد،شناسهٔ بازه ثبت و ادامه به p منتقل می‌شود؛ در غیر این صورت یک بازه عقب می‌رویم. در تساوی،قراردادِ فایل شاخهٔ حذفِ بازهٔ جاری را انتخاب می‌کند. این سیاست جواب را قطعی می‌کند،اما ادعای یکتاییِ جوابِ بهینه نیست.
خروجیِ اصلی C با ارزش۱۱ است. کد جدا بررسی می‌کند شناسه‌ها تکراری نباشند،هیچ جفتِ انتخاب‌شده هم‌پوشان نباشد و جمعِ ارزشِ witness با مقدار DP برابر باشد. چاپِ تنها عدد۱۱،این کنترلِ خودِ انتخاب‌ها را جایگزین نمی‌کند.
همهٔ هشت زیرمجموعه را بشماریم
برای سه بازه،تمام هشت زیرمجموعه ساخته می‌شود. oracle بدون استفاده از DP،تمام جفت‌های هر زیرمجموعه را با رابطهٔ end≤start کنترل و ارزش‌های مجاز را جمع می‌کند. بیشینهٔ این فهرست۱۱ است؛ نتیجهٔ greedy با۱۰ نیز واقعاً اجرا شده است.
آزمون‌های جدا شامل ورودی خالی،A وB با مرز مشترک،ارزشِ صفر،دو بازهٔ هم‌ارزش و یک مجموعهٔ پنج‌بازه‌ای‌اند. همهٔ زیرمجموعه‌های هرکدام بررسی می‌شوند. شش ترتیبِ ورودیِ سه بازه نیز بعد از مرتب‌سازی،کل نتیجهٔ یکسان می‌دهند؛ فقط یک ترتیبِ خوش‌شانس آزموده نشده است.
این برنامه چه چیزی را زمان‌بندی نمی‌کند؟
نسخهٔ آموزشی حداکثر۸بازه با زمان و ارزشِ صحیحِ محدود می‌پذیرد. طول صفر،پایانِ قبل از شروع،شناسهٔ تکراری و ارزش منفی در آزمون‌ها رد می‌شوند. هیچ تقویم،منبع مشترک،جابجاییِ زمان یا عملیات رزرو در کار نیست. زمان‌های داده‌شده را تغییر نمی‌دهیم؛ فقط انتخاب می‌کنیم.
کوله‌پشتی صفر و یک ظرفیتِ جمعیِ اندازه‌ها دارد؛ اینجا تعارضِ جفتیِ بازه‌ها تعیین‌کننده است. برای مسئلهٔ کسب‌وکار،تعارض نوبت و مرجع تأیید را در جلوگیری از رزرو هم‌زمان جدا بخوانید. ادامه در مبانی هوش مصنوعی؛ این تمرین بهینه‌سازِ نصب‌شده در محصول اپرا نیست.
فایل تمرین و منبع
کد مستقلِ تمرین و کنترل‌ها؛ Python · ورودی‌ها و تمام خروجی واقعیِ همین تمرین؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.