পাইথনে বুককেস শেলফ পূরণ সমস্যা

মনে করুন আমাদের একটি বইয়ের সিকোয়েন্স আছে — এখানে 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, কারণ ৩টি শেলফের হাইটের সম 1 + 3 + 2 = 6। লক্ষ্য করুন বই নম্বর ২ প্রথম শেলফে থাকতে হয় না।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (ডাইনামিক প্রোগ্রামিং):

books সাইজের একটি dp অ্যারে বানান, infinity দিয়ে পূরণ করুন।
dp[0] := books[0][1]
for i in range 1 to len(books) - 1:
- curr_height := 0, temp := shelf_width, j := i
- while j >= 0 and temp - books[j][0] >= 0:
  - curr_height := max(books[j][1], curr_height)
  - dp[i] := min(dp[i], curr_height + (dp[j-1] if j-1 >= 0 else 0))
  - temp -= books[j][0], j -= 1
return dp[-1]

উদাহরণ

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
        return dp[-1]

ইনপুট

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