Next-fit-decreasing bin packing
நெக்ஸ்ட்-ஃபிட்-டிக்ரீசிங் (என்எஃப்டி) என்பது தொட்டி பொதி செய்வதற்கான ஒரு வழிமுறையாகும். அதன் உள்ளீடு வெவ்வேறு அளவுகளின் பொருட்களின் பட்டியலாகும். அதன் வெளியீடு ஒரு பொதி ஆகும்-ஒவ்வொரு தொட்டியிலும் உள்ள பொருட்களின் அளவுகளின் கூட்டுத்தொகை அதிகபட்சமாக இருக்கும் வகையில், நிலையான திறன் கொண்ட தொட்டிகளாக பொருட்களைப் பிரிப்பது. வெறுமனே, முடிந்தவரை சில தொட்டிகளைப் பயன்படுத்த விரும்புகிறோம், ஆனால் தொட்டிகளின் எண்ணிக்கையைக் குறைப்பது ஒரு NP-கடினமான சிக்கலாகும். என்எஃப்டி வழிமுறை பின்வரும் ஹூரிஸ்டிக்கைப் பயன்படுத்துகிறதுஃ பொருட்களை மிகப்பெரியது முதல் சிறியது வரை வரிசைப்படுத்துங்கள். ஒரு வெற்று தொட்டியை துவக்கி அதை "திறந்த தொட்டி" என்று அழைக்கவும். ஒவ்வொரு பொருளுக்கும், அது திறந்த தொட்டியில் பொருந்துகிறதா என்று சரிபார்க்கவும்ஃ அது பொருந்தினால், புதிய பொருளை அதில் வைக்கவும். இல்லையெனில், தற்போதைய தொட்டியை மூடி, ஒரு புதிய தொட்டியைத் திறந்து, தற்போதைய பொருளை அதற்குள் வைக்கவும். சுருக்கமாகஃ என்எஃப்டி இறங்கு அளவு மூலம் பொருட்களை ஆர்டர் செய்கிறது, பின்னர் அடுத்த பொருத்தம் தொட்டி பேக்கிங் அழைக்கிறது. செயல்திறன் மேல் பிணைப்பு பேக்கர் மற்றும் காஃப்மேன் நிரூபித்தனர், ஒவ்வொரு முழு எண் r க்கும், அனைத்து பொருட்களின் அளவும் அதிகபட்சம் 1/r ஆக இருக்கும்போது, RFD இன் அறிகுறியற்ற தோராய விகிதம் திருப்தி அளிக்கிறது, அங்கு ஒரு வரிசை அதன் முதல் கூறுகள் தோராயமாக 1.69103,1.42312,1.30238 ஆகும். குறிப்பாக, r = 1 ஐ எடுத்துக்கொள்வது அதைக் குறிக்கிறது. பின்னர், என்எஃப்டியும் நிகழ்தகவு ரீதியாக பகுப்பாய்வு செய்யப்பட்டுள்ளது. மாறுபாடுகள் நெக்ஸ்ட்-ஃபிட் ஒரு பட்டியலையும் அதன் தலைகீழையும் அதே எண்ணிக்கையிலான தொட்டிகளில் தொகுக்கிறது. எனவே, நெக்ஸ்ட்-ஃபிட்-இன்க்ரீசிங், நெக்ஸ்ட்-ஃபிட்-டிக்ரீசிங் போன்ற அதே செயல்திறனைக் கொண்டுள்ளது. இருப்பினும், பொதுவான செலவு கட்டமைப்புகள் இருக்கும்போது அடுத்த-பொருத்தம்-அதிகரிப்பு சிறப்பாக செயல்படுகிறது. குறிப்புகள் தொட்டி பொதி