पायथन में बुककेस शेल्व्स भरना

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

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

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

• books के समान आकार का एक ऐरे dp बनाएं, और इसे अनंत से भरें
• dp[0] := books[0,1]
• i को 1 से books की लंबाई - 1 तक रेंज में
  • curr_height := 0
  • temp := shelf_width
  • j := i
  • जब तक j >= 0 और temp - books[j, 0] >= 0, करें
    • curr_height := books[j, 1] और curr_height का अधिकतम
    • dp[i] := dp[i] का न्यूनतम, curr_height + (dp[j - 1] यदि j - 1 >= 0, अन्यथा 0)
    • temp := temp - books[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