سوال ۵۹ کنکور ارشد مهندسی کامپیوتر ۱۴۰۴

فرض کنید مسئله‌ای با نام انتخاب پروژه‌های با بیشترین سود (Maximum Profit Project Selection) داریم. در این مسئله، تعدادی پروژه وجود دارد که هر پروژه دارای سود مشخص است و $m$ ماشین و یک محدودیت زمانی $T$ در اختیار داریم. می‌خواهیم تعدادی پروژه را برای انجام انتخاب کنیم به‌گونه‌ای که مجموع سود بیشینه شود و در عین حال محدودیت زمانی $T$ و ماشین‌های موجود رعایت شوند. برای یافتن جواب بهینه با روش انشعاب و تحدید (Branch and Bound) و هرس کردن شاخه‌های درخت جست‌وجو، باید برای هر گره یک حد بالا (Upper Bound) از بیشترین سود قابل دستیابی محاسبه شود. کدام گزینه حد بالای معتبری برای هر گره محاسبه می‌کند؟