वस्तुओं के समूह को 3 अलग-अलग समूहों में विभाजित करने के लिए एल्गोरिदम क्या है?

Question

मुझे अपनी पाठ्यपुस्तक में यह समस्या है: एन वस्तुओं के समूह को देखते हुए, प्रत्येक एक अलग मान V (i) के साथ, आइटम को 3 समूहों में विभाजित करने का सबसे अच्छा तरीका क्या है ताकि उच्चतम मूल्य वाले समूह को न्यूनतम किया जा सके? इस सबसे बड़े समूह का मूल्य दें।

मुझे पता है कि इस समस्या के 2 ढेर संस्करण को कैसे करें: इसे केवल समस्या पर पीछे की ओर एपगोरिदम चलाने की आवश्यकता है। हालांकि, मैं इस समस्या को हल करने के तरीके के बारे में बहुत परेशान हूं। क्या कोई मुझे कोई संकेत दे सकता है?

उत्तर: सुंदर ज्यादा 0-1 नैपसैक के रूप में एक ही बात है, हालांकि 2 डी

Answer 1

कठिन होमवर्क समस्या। यह अनिवार्य रूप से 3-विभाजन समस्या का अनुकूलन संस्करण है।

http://en.wikipedia.org/wiki/3-partition_problem

यह बारीकी से बिन पैकिंग, विभाजन, और सबसेट-राशि (और, जैसा कि आप का उल्लेख किया, नैपसैक) से संबंधित है। हालांकि, यह दृढ़ता से एनपी-पूर्ण होता है, जो इसे अपने चचेरे भाई से कठिन बनाता है। वैसे भी, मेरा सुझाव है कि आप संबंधित समस्याओं के लिए गतिशील प्रोग्रामिंग समाधान देखकर शुरू करें (मैं विभाजन के साथ शुरू करूंगा, लेकिन डीपी समाधान की गैर-विकिपीडिया स्पष्टीकरण पाएं)।

अद्यतन: मैं क्षमा चाहता हूं। मैंने तुम्हें गुमराह किया है। 3-विभाजन समस्या इनपुट को 3 के सेट में विभाजित करती है, न कि 3 सेट। मैंने जो कुछ भी कहा वह अभी भी लागू होता है, लेकिन नवीनीकृत आशा के साथ कि आपका संस्करण दृढ़ता से पूर्ण नहीं है।

Answer 2

मुझे "बेस्ट" गणितीय बोलने के बारे में पता नहीं है, लेकिन एक स्पष्ट दृष्टिकोण समूह के आबादी को प्रत्येक समूह में एक आइटम के साथ शुरू करना होगा। फिर, जब तक आपके पास अंतिम समूहों की वांछित संख्या की तुलना में अधिक समूह होते हैं, तो निम्न समूहों को निम्नतम मानों के साथ निकालें और उन्हें एक नए समूह में संयोजित करें जिसे आप संग्रह में वापस जोड़ते हैं। यह हफमैन संपीड़न के पेड़ों के निर्माण के समान है।

उदाहरण:

1 3 7 9 10 
becomes 
4(1+3) 7 9 10 
becomes 
9 10 11(1+3+7) 

Answer 3

Let च [मैं] [जे] [k] अर्थ है कि यह पहले सेट में मूल्य j और मूल्य कश्मीर दूसरे सेट में संभव है, के साथ पहले मैं आइटम करता हूं।

तो हमारे पास f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]] है।

और शुरुआत में हमारे पास f[0][0][0] = True है।

प्रत्येक f[i][j][k] = True के लिए, अपना उत्तर अपडेट करें कि आप को को कैसे परिभाषित करते हैं, इस पर निर्भर करता है।