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

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

• दिन 1:3, 2

• दिन 2:2, 4

• दिन 3:1, 4

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

• एक पुनरावर्ती फ़ंक्शन को हल करें () परिभाषित करें। यह वेट एरे, मैक्सवेट और शिप एरे लेगा, यह इस तरह काम करेगा -

• सूचकांक :=0

• मैं के लिए 0 से लेकर जहाजों की लंबाई तक की श्रेणी में

  • जहाज[i] :=0

  • जबकि सूचकांक <वजन और जहाजों की लंबाई [i] + भार [सूचकांक] <=अधिकतम वजन

    • जहाज़[i] :=जहाज़[i] + वज़न[सूचकांक]

    • इंडेक्स को 1 से बढ़ाएं

• सही लौटें, जब सूचकांक =भार की लंबाई, अन्यथा गलत

• मुख्य विधि इस तरह काम करेगी

• जहाज:=डी के समान आकार की एक सरणी, और इसे 0 से भरें

• अधिकतम वजन :=अधिकतम भार

• कम :=अधिकतम वजन, उच्च :=अधिकतम वजन + वजन सरणी की लंबाई + 1

• जबकि कम <उच्च

  • मध्य :=निम्न + (उच्च-निम्न)/2

  • यदि हल (वजन, मध्य, जहाज) सत्य है, तो उच्च:=मध्य, अन्यथा निम्न:=मध्य + 1

• उच्च वापसी

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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<high:
         mid = low + (high-low)//2
         if self.solve(weights,mid,ships):
            high = mid
         else:
            low = mid+1
      return high
   def solve(self,weights,max_w,ships):
      index = 0
      for i in range(len(ships)):
         ships[i] = 0
         while index < len(weights) and ships[i]+weights[index]<= max_w:
            ships[i] += weights[index]
            index+=1
      return index == len(weights)
ob = Solution()
print(ob.shipWithinDays([3,2,2,4,1,4],3))

इनपुट

[3,2,2,4,1,4]
3

आउटपुट

6