पायथन में बुककेस अलमारियों को भरना

मान लीजिए कि हमारे पास पुस्तकों का एक क्रम है - यहाँ i-th पुस्तक में मोटाई की पुस्तकें[i][0] और ऊँचाई वाली पुस्तकें[i][1] हैं। अगर हम इन किताबों को उन बुकशेल्फ़ पर रखना चाहते हैं जिनकी कुल चौड़ाई शेल्फ_चौड़ाई है। अगर हम इस शेल्फ पर रखने के लिए कुछ किताबें चुनते हैं (जैसे कि उनकी मोटाई का योग <=शेल्फ_चौड़ाई है), तो बुककेस के शेल्फ का एक और स्तर बनाएं जहां किताबों की अलमारी की कुल ऊंचाई अधिकतम ऊंचाई से बढ़ गई है किताबें हम नीचे रख सकते हैं। हम इस प्रक्रिया को तब तक दोहराते रहेंगे जब तक कि कोई और किताबें न हों। हमें यह ध्यान रखना होगा कि उपरोक्त प्रक्रिया के प्रत्येक चरण में हम जिस क्रम में पुस्तकों को रखते हैं, वही क्रम पुस्तकों के दिए गए क्रम का होता है। इस तरह से अलमारियों को रखने के बाद हमें न्यूनतम संभव ऊंचाई का पता लगाना होगा जो कुल बुकशेल्फ़ हो सकती है। तो अगर इनपुट की तरह है - [[1,1], [2,3], [2,3], [1,1], [1,1], [1,1], [1,2]] , और स्वयं_चौड़ाई =4,

तो आउटपुट 6 होगा क्योंकि 3 अलमारियों की ऊंचाई का योग 1 + 3 + 2 =6 है। ध्यान दें कि पुस्तक संख्या 2 को पहले शेल्फ पर नहीं होना चाहिए।

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

• एक सरणी डीपी बनाएं जिसका आकार किताबों के समान हो, और इसे अनंत का उपयोग करके भरें
• dp[0] :=किताबें[0,1]
• 1 से लेकर किताबों की लंबाई तक के लिए - 1
  • curr_height:=0
  • अस्थायी:=self_width
  • j :=i
  • जबकि j>=0 और अस्थायी - किताबें[j, 0]>=0, do
    • curr_height :=ज़्यादा से ज़्यादा किताबें[j, 1], curr_height
    • dp[i] :=min of dp[i], curr_height + (dp[j-1] अगर j – 1>=0, अन्यथा 0)
    • अस्थायी:=अस्थायी - किताबें[j, 0]
    • j को 1 से घटाएं
• dp का अंतिम तत्व लौटाएं

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

उदाहरण

class Solution(object):
   def minHeightShelves(self, books, shelf_width):
      """
      :type books: List[List[int]]
      :type shelf_width: int
      :rtype: int
      """
      dp = [float('inf') for i in range(len(books))]
      dp[0] = books[0][1]
      for i in range(1,len(books)):
         current_height = 0
         temp = shelf_width
         j = i
         while j>=0 and temp-books[j][0]>=0:
            current_height = max(books[j][1],current_height)
            dp[i] = min(dp[i],current_height +( dp[j-1] if j-1 >=0 else 0))
            temp-=books[j][0]
            j-=1
         #print(dp)
      return dp[-1]

इनपुट

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

आउटपुट

6