یک کوله‌پشتی با حجم $C$ و $n$ جعبه به شما داده شده است. حجم بسته $i$م را با $s_i$ و ارزش آن را با $v_i$ نشان می‌دهیم. می‌خواهیم تعدادی از جعبه‌ها را در کوله‌پشتی قرار دهیم، به شکلی که مجموع حجم‌ آن‌ها کمتر از $C$ باشد و مجموع ارزش آن‌ها بیشینه شود. فرض کنید $A$ برابر با مجموع ارزش‌ها در حالت بهینه باشد. الگوریتمی با پیچیدگی زمانی $O(n logn)$ ارائه دهید که یک چیدمان از جعبه‌ها با حجم حداکثر $C$ و ارزش حداقل $A/2$ پیدا کند.

• سوال بعد
• سوال قبل