یک کارخانه دارای یک سیستم بسته‌بندی کالا به شرح زیر است:

$n$ کالا که هر یک وزنی معادل $w_i$ دارد به ترتیبی از پیش تعیین‌شده، وارد مرکز بسته‌بندی می‌شود. در مرکز بسته‌بندی دو بسته‌ی باز قرار دارد که هر یک حداکثر $P$ واحد وزن را در خود جای می‌دهد. سیستم ما در برابر کالایی که وارد می‌شود این عکس‌العمل‌ها را می‌تواند نشان دهد:

1. آن را در یکی از بسته‌های (باالطبع به اندازه‌ی کافی خالی) فعلی قرار می‌دهد.
2. یکی از بسته‌ها را ببندد و کنار بگذارد و یک بسته‌ی خالی مشابه را به جایش قرار دهد و کالا را در آن قرار دهد.

در انتهای کار بسته‌های غیر خالی فعلی را هم بسته و کنار می‌گذاریم. هدف ما کم‌ کردن تعداد بسته‌هایی است که استفاده کرده‌ایم. الگوریتمی از $O(nP)$ طراحی کنید که با کم‌ترین تعداد بسته این کار را انجام دهد.

(توجه: به کسانی که تنها موقف به یافتن الگوریتم $O(nP^2)$ شوند، درصدی از نمره تعلق می‌گیرد.)

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