मुझे एक ऐसा एप्लिकेशन लिखने में दिलचस्पी है जो निर्धारित कर सकता है कि 10 लोगों को टेबल पर 2-10 लोगों के समूह कैसे बैठें। शायद कुल 15 टेबल और 140 लोग होंगे। मैं लोगों के किसी भी समूह को तोड़ना नहीं चाहता हूं।लोगों के समूहों को बैठने के लिए एल्गोरिदम?
ऐसा लगता है कि यह एक आम समस्या हो सकती है और मैं सोच रहा था कि अगर किसी के पास कोई समाधान है तो मुझे इस समाधान के लिए कहां देखना चाहिए। किसी भी लिंक या सुझाव की सराहना की।
यह bin packing problem है।
@ एबे मिस्सेलर, इस लिंक को देखें और _First-fit algorithm_ के बारे में पढ़ें। सामान्य समस्या कठिन है, लेकिन आपकी आकार सीमाएं निष्पक्ष, लालची दृष्टिकोण के साथ करना आसान बनाती हैं। – grossvogel
आकार सीमा यह आसान बनाता है अगर यह अनिर्धारित है - जिसका अर्थ है कि कई समाधान हैं। हालांकि, दूसरे चरम मामले में जहां सभी समूहों को दस तालिकाओं पर बैठना असंभव है (लेकिन केवल मुश्किल से), आपको यह निर्धारित करने के लिए हर संभवता को समाप्त करना होगा कि यह असंभव है। –
AFAIK, पहला फिट दृष्टिकोण यह है कि अधिकांश फाइल सिस्टम और मेमोरी मैनेजर अंतरिक्ष आवंटित करते समय उपयोग करते हैं, और यह काफी अच्छी तरह से काम करता है। – rmeador
समूह तय करें कि कहां बैठना है। क्या यह ठीक है अगर समूह अपने आप को तोड़ने, अन्य समूहों के साथ विलय करने, या तालिकाओं को एक साथ स्थानांतरित करने का निर्णय लेते हैं?
यदि यह एक शादी नहीं है, जहां दुल्हन और दुल्हन प्रत्येक टेबल के लिए भुगतान कर रहे हैं, और लोगों ने पहले से अनुरोध किया है कि वे क्या खाना चाहते हैं। –
नहीं, इसके लिए यह बहुत बड़ा नहीं है, अगर मैं उन्हें निर्णय लेने देता हूं कि समूह आमतौर पर टूट जाते हैं। –
पहले सबसे बड़े समूहों को वितरित करें, फिर जहां भी आप कर सकते हैं छोटे समूह जोड़ें। – mcandre
यह "Knapsack problem"
नहीं, यह नहीं है! Knapsack छद्म-बहुपद समाधान है जबकि बिन पैकिंग नहीं करता है। –
जब हम स्कूल में इस समस्या थी हम इसे एक समस्या के रूप में TSP के साथ हल मानक पर सिर्फ एक भिन्नता है।
इसका मतलब है कि समस्या एनपी-हार्ड है। तो अबे को शायद इष्टतम एल्गोरिदम नहीं मिलेगा ... – YuppieNetworking
@ युप्पी: नहीं, इसका मतलब है कि यह एनपी है, जो वास्तव में हमें कुछ भी नहीं बताता है * (हालांकि तथ्य यह है कि आपने बहुपद का उपयोग करने के बजाय कक्षा में टीएसपी के रूप में समस्या का मॉडल किया समय-समय पर एल्गोरिदम संकेत देता है कि प्रशिक्षक को पता था कि समस्या एनपी-पूर्ण है:) * –
यह bin packing problem है, जो एनपी-हार्ड है (सर्वोत्तम जवाब ढूंढना आसान नहीं है, और यह जांचना आसान नहीं है कि कोई जवाब सर्वोत्तम है या नहीं)।
लोगों के समूह समूह में लोगों की संख्या = मात्रा के साथ एक व्यक्तिगत वस्तुएं हैं। टेबल आकार 10 के डिब्बे हैं।
वहां कुछ अनुमानित एल्गोरिदम हैं, जो यह जानना आसान होना चाहिए कि आपको बिन पैकिंग के लिए Google होना चाहिए।
हालांकि, आपकी समस्या आराम से है (कुछ तरीकों से) क्योंकि आपके पास 10 टेबल हैं - यानी, आप कम से कम तालिकाओं पर लोगों को फिट करने की कोशिश नहीं कर रहे हैं। यदि 10 टेबल ऑप्टिकल समाधान है, तो आपको समाधान खोजने में परेशानी होगी (यदि यह भी मौजूद है), लेकिन अगर इष्टतम वास्तव में 7 या 8 है, तो समाधान ढूंढना आसान होगा। यह सब समूह वितरण पर निर्भर करता है।
इष्टतम 7 या 8 नहीं हो सकता है क्योंकि ~ 140 लोग हैं और तालिका का आकार 10 है। –
कृपया सर्वोत्तम परिभाषित करें। – IVlad
बेस्ट: ऑपरेशन हल करने के लिए ओ (0) लेता है। कोई गणना नहीं की गई! – mcandre
कोई समूह टूट नहीं गया है। हर समूह बैठे हैं। –