حل تشریحی سوال شماره 59 ساختمان داده‌ها

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