समस्या
प्रत्येक व्यक्ति को ठीक एक बार यात्रा करनी है। कोई भी समूह एक साथ यात्रा कर सकता है यदि उनके भार का योग क्षमता से अधिक न हो। लोगों को स्वतंत्र रूप से फिर से समूहित किया जा सकता है; उनकी इनपुट क्रम का कोई महत्व नहीं है। यात्राओं की संख्या को न्यूनतम करें।
elevator_rides(weights, capacity) को लागू करें।
इनपुट
weights: प्रत्येक व्यक्ति का भार।
capacity: एक यात्रा में अधिकतम कुल भार।
आउटपुट
न्यूनतम यात्राओं की संख्या लौटाएँ।
सीमाएँ
1 ≤ लोग ≤ 20। 1 ≤ क्षमता ≤ 1,000,000,000। प्रत्येक भार 1 और क्षमता के बीच है।
उदाहरण
इनपुट:
weights = [3, 4, 5]
capacity = 7
अपेक्षित आउटपुट:
expected = 2इनपुट:
std::vector<long long> weights = {3, 4, 5};
long long capacity = 7;
अपेक्षित आउटपुट:
long long expected = 2;इनपुट:
long[] weights = new long[] {3, 4, 5};
long capacity = 7;
अपेक्षित आउटपुट:
long expected = 2;व्याख्या
3 और 4 को एक साथ भेजें और 5 को अलग। कुल भार 12 है, जो 7 की क्षमता वाली एक यात्रा में नहीं आ सकता।
इनपुट:
weights = [2, 2, 2]
capacity = 6
अपेक्षित आउटपुट:
expected = 1इनपुट:
std::vector<long long> weights = {2, 2, 2};
long long capacity = 6;
अपेक्षित आउटपुट:
long long expected = 1;इनपुट:
long[] weights = new long[] {2, 2, 2};
long capacity = 6;
अपेक्षित आउटपुट:
long expected = 1;व्याख्या
तीनों लोग एक साथ आ सकते हैं क्योंकि 2 + 2 + 2 = 6।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
क्योंकि लोगों की संख्या छोटी है, individual rides की बजाय subsets पर विचार करो.
संकेत 2
हर subset के लिए track करो कि कितनी rides लगी हैं और current last ride कितना full है.
संकेत 3
जब दो states में rides की संख्या same हो, तो छोटी current load वाली state को prefer करो.
अपेक्षित जटिलता
समय O(2^n * n), अतिरिक्त स्थान O(2^n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।