लोगों के समूहों को व्यवस्थित रूप से व्यवस्थित करना

Question

मेरे पास यह होमवर्क असाइनमेंट है जो मुझे लगता है कि मैं हल करने में कामयाब रहा हूं, लेकिन पूरी तरह से सुनिश्चित नहीं हूं क्योंकि मैं अपना समाधान साबित नहीं कर सकता। मैं जो करता हूं उस पर टिप्पणियां चाहता हूं, इसकी शुद्धता और क्या कोई बेहतर समाधान है या नहीं।

समस्या निम्नानुसार है: हमारे पास N लोगों के समूह हैं, जहां समूह i में g[i] लोग हैं। हम इन लोगों को S सीटों की दो पंक्तियों पर रखना चाहते हैं, जैसे कि: प्रत्येक समूह को केवल एक पंक्ति में रखा जा सकता है, एक संगत अनुक्रम में, या यदि समूह में सदस्यों की संख्या भी है, तो हम उन्हें दो में विभाजित कर सकते हैं और उन्हें दो पंक्तियों पर रखें, लेकिन इस शर्त के साथ कि उन्हें एक आयताकार बनाना होगा (इसलिए उनके पास दोनों पंक्तियों पर एक ही सूचकांक होना चाहिए)। S सीटों की न्यूनतम संख्या क्या है ताकि कोई भी खड़ा न हो?

उदाहरण: समूह 4 11 हैं। न्यूनतम S11 है। हमने एक पंक्ति में सभी 4 और दूसरी पंक्ति पर 11 डाल दिया। एक और: समूह 6 2 हैं। हमने दो पंक्तियों पर और 0 दोनों पर 6 विभाजित किया। इसलिए 4 सीटें न्यूनतम है।

गणना T = (sum of all groups + 1)/2:

यह है कि मैं क्या सोच रहा हूँ है। समूह संख्याओं को सरणी में संग्रहीत करें, लेकिन के सभी मानों को x/2 के दो मानों में विभाजित करें। तो 4 52 2 5 बन जाता है। अब इस वेक्टर पर subset sum चलाएं, और T से अधिक या उसके बराबर न्यूनतम मान प्राप्त करें जिसे बनाया जा सकता है। वह मूल्य प्रति पंक्ति सीटों की न्यूनतम संख्या आवश्यक है।

उदाहरण: 4 11 => 2 2 11 => T = (15 + 1)/2 = 8। न्यूनतम हम 2 2 11 से बना सकते हैं जो >= 811 है, इसलिए यह उत्तर है।

ऐसा लगता है कि कम से कम मुझे कोई काउंटर उदाहरण नहीं मिल रहा है। हालांकि मेरे पास सबूत नहीं है। सहजता से, इस एल्गोरिदम द्वारा प्रदान की गई सीटों की संख्या के साथ लोगों को आवश्यक शर्तों के तहत व्यवस्था करना हमेशा संभव होता है।

किसी भी संकेत की सराहना की जाती है।

Answer 1

मुझे लगता है कि आपका समाधान सही है। इष्टतम वितरण में प्रति पंक्ति सीटों की न्यूनतम संख्या आपके टी (जो गणितीय रूप से स्पष्ट है) होगी।

संख्याओं को विभाजित करना भी सही है, क्योंकि उनके पास दो संभावित व्यवस्थाएं हैं; सीट पंक्तियों के एक छोर पर लोगों के सभी "आयताकार" समूहों को तार्किक रूप से डालकर आप यह भी गारंटी दे सकते हैं कि वे हमेशा एक उचित आयताकार बनाएंगे, ताकि यह स्थिति भी मिल सके।

तो प्रश्न टी के बराबर बराबर या करीब (जैसे partition problem) खोजने के लिए उबलता है।

Answer 2

माइनर निट: मुझे यकीन है कि नहीं कर रहा हूँ अगर बढ़त मामले में जहां प्रत्येक समूह, 0 सदस्य हैं हमेशा सकारात्मक है T = SUM ALL + 1/2 में अपने अंश क्योंकि, इसलिए एक सबसेट राशि तुलना में अधिक है वहाँ कभी नहीं होगा में काम करता है ऊपर प्रस्तावित समाधान या T के बराबर।

इसके आसपास पाने के लिए, शायद एक मॉड्यूलस ऑपरेशन यहां काम कर सकता है। हम जानते हैं कि हमें कम से कमn सीटों में पंक्तियों की आवश्यकता है यदि n अधिकतम विषम शब्द है, तो शायद समीकरण में max(n * (n % 2)) शब्द होना चाहिए।यह max(odd) या 0 पर आ जाएगा। चूंकि अधिकतम विषम शब्द हमेशा S में जोड़ा जाता है, मुझे लगता है कि यह सुरक्षित है (सबूत के बिना साहसपूर्वक कहा गया है ...)।

फिर हम जानना चाहते हैं कि हमें भी शर्तों को विभाजित करना चाहिए या नहीं। यहां वह जगह है जहां सबसेट योग दृष्टिकोण काम कर सकता है, लेकिन T के साथ बस SUM ALL/2 के बराबर है।