بسته بندی سطلی

(Bin packing)

*تعدادی شئ با اندازه‌های بین ۰ و ۱ داریم می‌خواهیم آنها را در کمترین تعداد سطل با اندازه یک جا بدهیم.

این مسأله را نمی‌توان در زمان چندجمله‌ای بهینه حل کرد، اما می‌خواهیم نسخه‌ی دیگری از آن را بسازیم که در زمان چندجمله‌ای قابل حل است و از آن برای تقریب زدن مسأله اصلی استفاده کنیم.

*تعدادی شئ با اندازه‌های بین e(اپسیلون) و ۱ داریم که حداکثر K اندازه مختلف دارند و می‌خواهیم آنها را در کمترین تعداد سطل با اندازه یک جا بدهیم.

این مسأله را می‌توان در زمان چندجمله‌ای به صورت بهینه حل کرد. راه حل بهینه برای حل کردن آن امتحان کردن همه‌ی حالت‌های ممکن است.

شرطی که روی حداقل اندازه‌ی اشیا گذاشتیم باعث محدود شدن حداکثر تعداد اشیای هر سطل می‌شود:

تعداد حالت‌های مختلف هر سطل را به صورت زیر حساب می‌کنیم:

تعداد حالت‌های R سطل متفاوت را هم به صورت زیر حساب می‌کنیم:

پس تعداد کل حالت‌های مسأله چندجمله‌ای شد. دقت کنید که توان (R) به اپسیلون وابسته است و n اندازه مسأله ورودی است.

*حالا می‌خواهیم مسأله‌ی اصلی را تنها با شرط اضافه وزن اشیا بیشتر مساوی اپسیلون را با کمک این مسأله حل کنیم. برای این کار باید تعداد وزن‌های متمایز اشیا حداکثر K شود.

راه حل ۱ که خوب نیست: وزن اشیا را بر p/K تقسیم می‌کنیم که p ماکسیمم وزن اشیا است. با این کار وزن اشیا از بازه‌ی ۰ تا p به بازه‌ی ۰ تا K می‌رود. حداکثر تقریبی که این کار در وزن اشیا ایجاد می‌کند p/K است. (چون جزء اعشاری بین ۰ و ۱ است.) این مقدار تقریب مورد نظر ما در مسأله نیست و متاسفانه به p هم بستگی پیدا می‌کند.

راه حل ۲: در روش قبل ما تعداد وزن‌هایی که داریم احتمالا خیلی از K کمتر خواهد بود (چون در صورتی که همه‌ی وزن‌ها اعداد متوالی باشند K می‌شود). به همین دلیل مسأله را به چند زیرمسأله از مسأله‌ی حالت خاص که می‌توانیم آن را حل کنیم تبدیل می‌کنیم. این کار را طوری انجام می‌دهیم که شرط قبلی حفظ شود یعنی در هر دسته حداکثر K اندازه متمایز داشته باشیم.

حداکثر تعداد زیرمسأله‌های ساخته شده Q است (که در زیر مقدار آن آمده است). حالا K را طوری تعیین می‌کنیم ضریب تقریب مجموع وزن اشیا در جواب بهینه و این جواب حداکثر به اندازه اپسیلون فرق داشته باشد.

* حل مسأله اصلی

ما هنوز از یکی از اطلاعاتی که از مسأله داریم استفاده نکرده‌ایم. اگر اشیا وزن بیشتر مساوی ۰.۵ داشته باشند، می‌توانیم جواب بهینه آن را در زمان خطی به دست بیاوریم. چون در هر سطل حداکثر یک شئ قرار می‌گیرد. اگر اشیا وزن کمتر از ۰.۵ داشته باشند، آنها را حریصانه در جعبه‌ها می‌چینیم و به الگوریتم با ضریب تقریب ۱+۲*اپسیلون می‌رسیم.

مسأله را به دو قسمت تقسیم می‌کنیم: اشیای با وزن بیشتر از اپسیلون و اشیای با وزن کمتر مساوی اپسیلون

ثابت می‌کنیم اضافه کردن اشیای با وزن کمتر مساوی اپسیلون ضریب تقریب الگوریتم قبل را به هم نمی‌زند.