समस्या इस प्रकार है (अनुवाद) को सुलझाने: परएक अनुकूलन (हर किसी को प्राप्त करने के लिए आवश्यक समय की है और एक पहाड़ के नीचे न्यूनतम राशि का पता लगाएं)
n रहे हैं (एन < = 25000) लोग एक पहाड़ के नीचे, और हर कोई पहाड़ के नीचे, ऊपर जाना चाहता है। 2 टूर गाइड हैं: एक व्यक्ति को पहाड़ पर जाने में मदद करने के लिए, एक व्यक्ति को नीचे जाने में मदद करने के लिए। जिस व्यक्ति को मैं लेता हूं (i) इस पर्वत पर चढ़ने का समय, और नीचे (i) इसे उतरने का समय। हालांकि, प्रत्येक गाइड केवल एक समय में 1 व्यक्ति की सहायता कर सकती है (जिसका अर्थ है कि अधिकतम 1 व्यक्ति चढ़ाई कर सकता है, और अधिकतर 1 व्यक्ति किसी भी समय पहाड़ पर उतर सकता है)। मान लें कि जब "अप" गाइड शीर्ष तक पहुंच जाता है, तो उसे तुरंत नीचे "नीचे" गाइड के साथ नीचे भेज दिया जाता है। हर किसी को ऊपर उठाने और पहाड़ पर वापस जाने के लिए कम से कम समय लगता है। इनपुट करने के लिए
3 persons person 1: up=6 minutes, down=4 minutes person 2: up=8 minutes, down=1 minutes person 3: up=2 minutes, down=3 minutesआउटपुट:: मेरे द्वारा
यहाँ एनोटेशन के साथ, समस्या के लिए एक नमूना इनपुट है (लोग पहाड़ यदि आवश्यक हो के शीर्ष पर एकत्र कर सकते हैं)
न्यूनतम समय 17 है। ऐसा इसलिए है क्योंकि यदि व्यक्ति 3 पहले जाता है, तो व्यक्ति 1, और फिर व्यक्ति 2 (और यह वही आदेश दोनों चढ़ाई और वंश दोनों के लिए उपयोग किया जाता है), यह कुल समय 17
देता है (एनएक हे:
मैं कोशिश में कुछ एल्गोरिदम के साथ आ गया है, लेकिन यहाँ क्या मैं अब तक है है! * एन) एल्गोरिदम: अगली_प्रर्म्यूशन
एक लालची एल्गोरिदम: मैंने लोगों को अवरोही समय कम करके लोगों को हल किया है, और उन्हें एक साथ रखने की कोशिश की है, लेकिन इसका परिणाम सही समाधान नहीं हुआ है।
अन्य विचारों
मैं अब गतिशील प्रोग्रामिंग की ओर कर रहा हूँ, CLR के अनुसार के रूप में, अनुकूलन समस्याओं आमतौर पर लालची या गतिशील प्रोग्रामिंग (इस समस्या, मुझे लगता है, संतुष्ट इष्टतम उपसंरचना) कर रहे हैं।
मैंने देखा है कि न्यूनतम समाधान में, "अप" मार्गदर्शिका में तब तक आराम नहीं होगा जब तक कि हर कोई पहाड़ पर न हो। (इसलिए व्यक्ति 1 की चढ़ाई, व्यक्ति 2 की चढ़ाई, आदि के बीच कोई अंतराल नहीं है ..) शायद मूल समय के बीच अंतराल को कम करने के लिए समस्या को कम किया जा सकता है?
मुझे इस गतिशील प्रोग्रामिंग समस्या के लिए एक राज्य को चित्रित करने में परेशानी हो रही है, (मुझे नहीं लगता कि यह एकल आयामी है, क्योंकि मुझे नहीं लगता कि आप मेरे लिए इष्टतम समाधान को जानने के लिए इष्टतम समाधान पा सकते हैं। -1 व्यक्ति)।
क्या कोई मदद कर सकता है?
सिर्फ एक अंतर्ज्ञान जो दूसरों का उपयोग कर सकता है: उस समस्या को किसी अन्य तरीके से सोचना बेहतर हो सकता है: डाउन गाइड के निष्क्रिय समय को कम करें (ऊपर मार्गदर्शिका कभी नहीं रुक जाती है)। – GameAlchemist
गाइड समस्या के लिए, मैं यही सोच रहा था, नीचे गाइड को उन लोगों को शीर्ष पर ले जाना चाहिए जिनके पास सबसे कम समय है। अप गाइड को व्यक्ति को सबसे कम समय के साथ ले जाना चाहिए, सिवाय इसके कि इसे किसी ऐसे व्यक्ति को नहीं लेना चाहिए जो ऊपर जाने से कम समय लेता है, जब तक कि शीर्ष पर प्रतीक्षा करने वाले लोगों की कतार के साथ समय अंतर नहीं बनाया जा सकता है या उन लोगों को लेने के अलावा कोई अन्य विकल्प नहीं है जो कम समय से नीचे जा रहे हैं। –
मुझे लगता है कि यह प्रकार लोगों की संख्या और कितने समय पर निर्भर करता है पर निर्भर करता है। यदि आपको शीर्ष पर कतार नहीं है, तो डाउन गाइड होने से सबसे लंबा समय व्यक्ति पहले बेहतर हो सकता है। दिलचस्प विचार अभ्यास। –