Next-fit-decreasing bin packing
نیکسٹ فٹ ڈیکریزنگ (این ایف ڈی) بن پیکنگ کے لیے ایک الگورتھم ہے۔ اس کا ان پٹ مختلف سائز کی اشیاء کی فہرست ہے۔ اس کی پیداوار ایک پیکنگ ہے-اشیاء کو مقررہ گنجائش کے ڈبوں میں تقسیم کرنا، اس طرح کہ ہر ڈبے میں موجود اشیاء کے سائز کا مجموعہ زیادہ سے زیادہ گنجائش پر ہو۔ مثالی طور پر، ہم زیادہ سے زیادہ کم ڈبے استعمال کرنا چاہیں گے، لیکن ڈبوں کی تعداد کو کم کرنا ایک این پی سخت مسئلہ ہے۔ این ایف ڈی الگورتھم مندرجہ ذیل ہیورسٹک کا استعمال کرتا ہے: اشیاء کو سب سے بڑے سے چھوٹے تک آرڈر کریں۔ ایک خالی ڈبے کو شروع کریں اور اسے "اوپن ڈبے" کہیں۔ ترتیب میں ہر آئٹم کے لیے، چیک کریں کہ آیا یہ کھلے ڈبے میں فٹ ہو سکتا ہے: اگر یہ فٹ ہو تو نئی آئٹم کو اس میں رکھیں۔ ورنہ، موجودہ ڈبے کو بند کریں، ایک نیا ڈبے کھولیں، اور موجودہ چیز کو اس کے اندر رکھیں۔ مختصرا: این ایف ڈی اشیاء کو نیچے کی طرف آرڈر کرتا ہے، اور پھر نیکسٹ فٹ بن پیکنگ کو کال کرتا ہے۔ کارکردگی اوپری باؤنڈ بیکر اور کوفمین نے ثابت کیا کہ، ہر عدد r کے لیے، جب تمام آئٹمز کا سائز زیادہ سے زیادہ 1/r ہوتا ہے، تو RFD کا آسپٹوٹک تخمینہ تناسب مطمئن ہوتا ہے، جہاں ایک ترتیب ہے جس کے پہلے عناصر تقریبا 1.69103، 1.42312، 1.30238 ہیں۔ خاص طور پر، r = 1 لینے سے یہ ظاہر ہوتا ہے۔ بعد میں، این ایف ڈی کا بھی ممکنہ طور پر تجزیہ کیا گیا ہے۔ متغیرات نیکسٹ فٹ ایک فہرست اور اس کے الٹا کو اسی تعداد میں ڈبوں میں پیک کرتا ہے۔ لہذا، نیکسٹ فٹ انکریزنگ کی وہی کارکردگی ہے جو نیکسٹ فٹ ڈیکریزنگ کی ہے۔ تاہم، جب عام لاگت کے ڈھانچے ہوتے ہیں تو نیکسٹ فٹ انکریزنگ بہتر کارکردگی کا مظاہرہ کرتی ہے۔ حوالہ جات بن پیکنگ