पुस्तक "Algorithm Design Manual" से एक उत्पाद है।एल्गोरिदम - बिन-पैकिंग, एन ऑब्जेक्ट्स पैक करने के लिए डिब्बे व्यवस्थित करें
बिन-पैकिंग समस्या में, हमें एन धातु वस्तुओं को दिया जाता है, प्रत्येक वजन शून्य और एक किलोग्राम के बीच होता है। हमारा लक्ष्य उन छोटी-छोटी संख्या में डिब्बे ढूंढना है जो एन ऑब्जेक्ट्स को पकड़ेंगे, प्रत्येक बिन में अधिकतम एक किलोग्राम होगा।
बिन पैकिंग के लिए सबसे अच्छा हेरिस्टिक निम्नानुसार है। ऑब्जेक्ट्स को उस क्रम में मानें जिसमें उन्हें दिया गया है। प्रत्येक ऑब्जेक्ट के लिए, ऑब्जेक्ट डालने के बाद के बाद को आंशिक रूप से भरे बिन में अतिरिक्त कक्ष के साथ रखें। यदि कोई ऐसा बिन मौजूद नहीं है, तो नया बिन प्रारंभ करें। एक एल्गोरिदम तैयार करें जो ओ (nlogn) समय में सर्वोत्तम फिट हेरिस्टिक (एन वजन के रूप में w1, w2, ..., wn और इनपुट का उपयोग आउटपुट) को इनपुट करता है।
ठीक है, यह उत्पाद कठिन नहीं लगता है। मेरी प्रारंभिक समझ यह है कि सर्वोत्तम फिट हेरिस्टिक दृष्टिकोण के लिए, मैं हर बार न्यूनतम उपलब्ध स्थान के साथ एक बिन की तलाश करता हूं और वस्तु को अंदर रखने की कोशिश करता हूं। यदि वस्तु न्यूनतम स्थान के साथ बिन में फिट नहीं होती है, तो मैं एक नया बना देता हूं बिन।
मैं डिब्बे को स्टोर करने के लिए एक बीएसटी बना सकता हूं और प्रत्येक बार जब किसी ऑब्जेक्ट को बिन में रखा जाता है, तो मैं उस बिन को पेड़ से हटा सकता हूं, बिन के उपलब्ध स्थान को अपडेट कर सकता हूं और पेड़ को बिन को फिर से सम्मिलित कर सकता हूं। यह प्रत्येक ऑब्जेक्ट प्लेसमेंट के लिए ओ (लॉगएन) प्राप्त करेगा।
हालांकि, मैंने उत्पाद के बोल्ड और इटैलिक भाग को देखा "प्रत्येक ऑब्जेक्ट के लिए, ऑब्जेक्ट डालने के बाद की अतिरिक्त मात्रा के साथ इसे आंशिक रूप से भरे बिन में रखें"।
तो इसका मतलब है कि मैं एक बिन की तलाश नहीं कर रहा हूं जिसमें न्यूनतम उपलब्ध स्थान है, इसके बजाय, मैं एक की तलाश कर रहा हूं कि यदि मैं वर्तमान वस्तु को रखता हूं, परिणामी उपलब्ध स्थान (ऑब्जेक्ट रखने के बाद) न्यूनतम होगा।
उदाहरण के लिए, यदि bin1 की वर्तमान स्थान 0.5 है, तो bin2 0.7 है। तो वर्तमान में, bin1 न्यूनतम है। लेकिन यदि वर्तमान ऑब्जेक्ट 0.6 है, तो ऑब्जेक्ट को नया बिन बनाने के बजाय bin1 में नहीं रखा जा सकता है, मुझे ऑब्जेक्ट को bin2 - object = 0.7 - 0.5 = 0.2 के रूप में रखने के लिए bin2 को ढूंढना होगा जो न्यूनतम है।
क्या मैं सही हूँ? क्या कथन का बोल्ड हिस्सा वास्तव में मेरे जैसा सोचा है? या यह उतना आसान है जितना "न्यूनतम स्थान वाला बिन ढूंढें, यदि ऑब्जेक्ट रख सकता है, तो जगह; अगर नहीं, तो नया बिन बनाएं"?
धन्यवाद
संपादित करें: बोल्ड भाग की मेरी नई समझ के लिए अपने जावा कोड का हिस्सा जोड़ने।
public void arrangeBin(float[] w) {
BST bst = new BST();
bst.root = new Node();
int binCount = 0;
for (int i = 0;i < w.length;i++) {
float weight = w[i];
Node node = bst.root;
float minDiff = 1;
Node minNode = null;
while(node!=null) {
if (node.space > weight) {
float diff = node.space - weight;
if (minDiff > diff) {
minDiff = diff;
minNode = node;
node = node.left;
}
}
else
node = node.right;
}
if (minNode == null) {
binCount++;
Node node = new Node();
node.space -= weight;
bst.insert(node);
}
else {
minNode.space -= weight;
bst.delete(minNode);
bst.insert(minNode);
}
}
}
आपका कोड प्रत्येक नए वजन के लिए सभी नोड्स पर जाता है, जिसके परिणामस्वरूप ओ (एन 2) का समय चल रहा है। यदि आप ओ (nlogn) प्राप्त करना चाहते हैं तो आपको कुछ जवाब देना चाहिए जैसा मैंने अपने उत्तर में सुझाया था। इसके अलावा यह सही दिखता है। – WeaselFox
@WeaselFox, मैंने बोल्ड स्टेटमेंट के अनुसार, एक बीएस –