पायथन में D दिनों के भीतर पैकेज शिप करने की क्षमता

मान लीजिए एक कन्वेयर बेल्ट पर पैकेज हैं जिन्हें D दिनों के भीतर एक पोर्ट से दूसरे पोर्ट पर शिप किया जाएगा। यहां कन्वेयर बेल्ट पर i-वां पैकेज का वजन weights[i] है। प्रत्येक दिन, हम शिप को बेल्ट पर पैकेज के साथ लोड करेंगे। हम शिप की अधिकतम वजन क्षमता से अधिक वजन लोड नहीं करेंगे। हमें शिप की सबसे कम वजन क्षमता ढूंढनी है जिसके परिणामस्वरूप कन्वेयर बेल्ट पर सभी पैकेज D दिनों के भीतर शिप हो जाएंगे। इसलिए यदि इनपुट [3,2,2,4,1,4] और D = 3 है, तो आउटपुट 6 होगा, क्योंकि 6 की शिप क्षमता 3 दिनों में सभी पैकेज शिप करने के लिए न्यूनतम है, जैसे -

• दिन 1: 3, 2

• दिन 2: 2, 4

• दिन 3: 1, 4

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• solve() नामक एक रिकर्सिव फंक्शन परिभाषित करें। यह weights ऐरे, maxWeight, और ships ऐरे लेगा, यह इस तरह कार्य करेगा -

• index := 0

• i को 0 से ships ऐरे की लंबाई तक रेंज में

  • ships[i] := 0

  • जब तक index < weights की लंबाई और ships[i] + weights[index] <= maxWeight

    • ships[i] := ships[i] + weights[index]

    • index को 1 से बढ़ाएं

• true लौटाएं, जब index = weights की लंबाई, अन्यथा false

• मुख्य मेथड इस तरह कार्य करेगा

• ships := D के समान आकार का एक ऐरे, और इसे 0 से भरें

• maxWeight := weights का अधिकतम

• low := maxWeight, high := maxWeight + weights ऐरे की लंबाई + 1

• जब तक low < high

  • mid := low + (high - low)/2

  • यदि solve(weights, mid, ships) true है, तो high := mid, अन्यथा low := mid + 1

• high लौटाएं

उदाहरण

class Solution(object):
    def shipWithinDays(self, weights, D):
        ships = [0 for i in range(D)]
        max_w = max(weights)
        low = max_w
        high = max_w * len(weights)+1
        while low
इनपुट
[3,2,2,4,1,4] 3
आउटपुट
6