मुझे एक दिलचस्प प्रोग्रामिंग समस्या का सामना करना पड़ा है जिसका समाधान मैं तैयार नहीं कर सकता। मान लीजिए आपके पास N अलग-अलग रंगों की K गेंदें हैं। आपको सभी गेंदों को अधिक से अधिक समूहों में विभाजित करना चाहिए ताकि कोई भी दो समूह समान न हों। (दो समूहों को समान माना जाता है यदि उनके पास प्रत्येक रंग की गेंदों की संख्या समान है।) आप अधिकतम कितने समूह बना सकते हैं?

बाधाएं: 1<=K<=50, 1<=N<=14

स्पष्ट करने के लिए: हम एक एल्गोरिथ्म चाहते हैं जो पूर्णांकों की एक सरणी लेता है> = 1. सरणी का आकार N है और इसमें शामिल मानों का योग K है। एल्गोरिथ्म को समूहों की अधिकतम संख्या वापस करनी चाहिए।

इस समस्या के लिए एल्गोरिदमिक दृष्टिकोण पर कोई विचार?

12
TheDarBear 27 जून 2017, 23:12

2 जवाब

सबसे बढ़िया उत्तर

अपने प्रोफेसर से दोबारा बात करने के बाद, मुझे पता चला कि यह एक open.kattis.com problem

दोनों लगभग समान हैं, क्योंकि मूल समस्या के किसी भी उदाहरण को N के अभाज्य गुणनखंड को लेकर और प्रत्येक अभाज्य कारक को गेंद के रूप में मानकर हल किया जा सकता है। उदाहरण के लिए, 900 = 2^2*3^2*5*2, तो समतुल्य गेंदों की समस्या 2 2 2 होगी।

दी गई सीमा 10^15 की अधिकतम सीमा का उपयोग करते हुए पाई गई। 2^50> 10^15, इसलिए 50 से अधिक कारक कभी नहीं हो सकते हैं, और पहले 15 प्राइम को एक दूसरे से गुणा करना भी 10^15 से अधिक हो सकता है, जिसका अर्थ है कि अधिकतम 14 समूह हो सकते हैं।

गेंदों की संख्या और समूहों की संख्या के बीच के ट्रेडऑफ़ को हालांकि अनदेखा कर दिया गया था, और मेरी राय में यह समस्या को हल करना बहुत आसान बनाता है। उदाहरण के लिए, यदि 14 समूह हैं, तो प्रत्येक समूह में केवल 1 गेंद होगी, जबकि यदि 50 गेंदें हैं तो वे सभी एक ही समूह से संबंधित होंगी (यह मूल समस्या की 10^15 बाधाओं के कारण है)

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

ऐसा करने के बाद, अधिकतम मामलों में समस्या अभी भी बहुत धीमी थी, और एक अतिरिक्त अनुकूलन की आवश्यकता थी। मैंने पाया कि एक इष्टतम समाधान हमेशा मौजूद होता है जो जितना संभव हो उतने एकल गेंद समूहों का उपयोग करता है। शुरुआत में ज्यादा से ज्यादा 1 बॉल ग्रुप बनाकर और बाकी सब प्रॉब्लम को सॉल्व करके, मैं कट्टिस के समय की कमी में समस्या को पूरा करने में सक्षम था।

मेरा एल्गोरिथ्म दो मान्यताओं पर निर्भर करता है जिन्हें मैंने सिद्ध किया है:

  1. यदि आप सभी गेंदों का उपयोग किए बिना X समूह बना सकते हैं, तो आप सभी गेंदों का उपयोग करके X समूह भी बना सकते हैं। यह नैपसैक समाधान बनाता है जहां आप क्षमता का 100% वैध उपयोग नहीं करते हैं। सभी अप्रयुक्त गेंदों को लेकर और उन सभी को सबसे बड़े समूह में जोड़कर इस धारणा को सिद्ध किया जा सकता है। यह किसी भी अन्य से बड़ा समूह बनाएगा, और इसलिए यह अद्वितीय होना चाहिए। यह आपको समान संख्या में समूहों के साथ छोड़ देता है, लेकिन सभी गेंदों का उपयोग किया जाता है।

  2. जितना संभव हो उतने 1-गेंद समूहों का उपयोग करके हमेशा एक इष्टतम समाधान मौजूद होता है। यह मूल समस्या को समय की कमी में हल करने योग्य उप-समस्या में कम करना संभव बनाता है। यह भी सिद्ध किया जा सकता है। कोई भी इष्टतम समाधान लें। किसी भी 1 बॉल ग्रुपिंग के लिए जो मौजूद नहीं है, उस 1 बॉल वाले ग्रुप को लें और उस ग्रुप की हर दूसरी बॉल को सबसे बड़े ग्रुप में ले जाएं। यह समान (इष्टतम) समूहों की संख्या के साथ एक समाधान बनाता है, जिसमें अधिक से अधिक 1 बॉल समूह भी होते हैं।

मेरे समाधान में ओ (एफ (एन) ^ 2) का रनटाइम है, जहां एफ (एन) एन के कारकों की कुल संख्या है।

1
user2659185 5 जुलाई 2017, 06:22

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

  1. अधिक विशिष्ट परिणाम जीतता है (उदाहरण के लिए दो समूह जो दो समूहों पर एक नए विशिष्ट समूह से जुड़ते हैं जो पहले से ज्ञात एक से जुड़ते हैं)
  2. छोटा परिणाम जीतता है (उदाहरण के लिए तीन-तत्व समूहों पर दो-तत्व समूह)
  3. हटाने के लिए सबसे आम समूह

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

उदाहरण (प्रत्येक पंक्ति घटनाओं की संख्या के अनुसार क्रमित):

b  g-g-g  r-r-r-r  m-m-m-m-m  y-y-y-y-y-y-y  c-c-c-c-c-c-c-c-c-c
b  cc  g-g-g  r-r-r-r  m-m-m-m-m  y-y-y-y-y-y-y  c-c-c-c-c-c-c-c
b  cc  cy  g-g-g  r-r-r-r  m-m-m-m-m  y-y-y-y-y-y  c-c-c-c-c-c-c
b  cc  cy  cm  g-g-g  r-r-r-r  m-m-m-m  y-y-y-y-y-y  c-c-c-c-c-c
b  cc  cy  cm  yy  g-g-g  r-r-r-r  m-m-m-m  y-y-y-y  c-c-c-c-c-c
b  cc  cy  cm  yy  cr  g-g-g  r-r-r  m-m-m-m  y-y-y-y  c-c-c-c-c
b  cc  cy  cm  yy  cr  cg  g-g  r-r-r  m-m-m-m  y-y-y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  g-g  r-r-r  m-m-m  y-y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  rm  g-g  r-r  m-m  y-y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  rm  g  yg  r-r  m-m  y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m-m  c-c-c-c
b  cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m-m  cc-cc  c-c
b  cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m  cc  mcc  c-c
cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m  cc  mcc  c  cb
g-g-g  r-r-r-r-r  b-b-b-b-b
rb  g-g-g  r-r-r-r  b-b-b-b
rb  rg  g-g  r-r-r  b-b-b-b
rb  rg  br  g  r-r-r  b-b-b
rb  rg  br  g  r  rr  b-b-b
rb  rg  br  g  r  rr  b  bb

प्रत्येक चरण के लिए एक एल्गोरिथ्म के रूप में, मैंने उपरोक्त तुलना फ़ंक्शन द्वारा उन्हें हटाने और उन्हें आदेश देने के लिए समूहों के सभी संभावित संयोजनों को उत्पन्न नहीं किया, लेकिन कुछ उम्मीदवारों को प्राप्त करने के लिए पीछे की ओर चला गया:

  1. सबसे आम समूह चुनें और एक को हटा दें, फिर (अब) सबसे आम समूह चुनें और एक को हटा दें
  2. देखें कि उनके पास एक साथ अधिक तत्व नहीं हैं जो कम सामान्य समूहों के साथ प्राप्त किए जा सकते हैं
  3. देखो कि वे एक अज्ञात समूह से जुड़ते हैं
  4. यदि हां, तो उन्हें लें, यदि नहीं तो चरण 1 से अगले सामान्य समूहों के साथ दोहराएं

यह मूल रूप से प्रश्न पूछता है

  • यह समूह (तत्वों का संयोजन) कितना सामान्य है / इसकी संख्या कितनी है?
  • क्या इस समूह के तत्वों के साथ एक निश्चित आकार से कम के सभी संभावित संयोजन पहले ही उत्पन्न हो चुके हैं?
  • क्या इस समूह के तत्वों और अगले समूहों के तत्वों के साथ संभावित संयोजन पहले ही उत्पन्न हो चुके हैं?

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

1
Bergi 29 जून 2017, 04:13