Làm đầy kệ tủ sách bằng Python

Giả sử chúng ta có một dãy sách - Ở đây sách thứ i có sách chiều dày [i] [0] và sách chiều cao [i] [1]. Nếu chúng ta muốn đặt những cuốn sách này theo thứ tự trên giá sách có tổng chiều rộng là kệ_thông. Nếu chúng ta chọn một số sách để đặt trên giá này (sao cho tổng chiều dày của chúng là <=helf_width), thì hãy xây dựng một tầng giá khác của tủ sách trong đó tổng chiều cao của tủ sách đã tăng lên bằng chiều cao tối đa của sách chúng ta có thể đặt xuống. Chúng tôi sẽ lặp lại quy trình này cho đến khi không còn sách nào để đặt. Chúng ta phải ghi nhớ rằng ở mỗi bước của quy trình trên, thứ tự của những cuốn sách mà chúng ta đặt cũng giống như thứ tự của những cuốn sách đã cho. Chúng ta phải tìm chiều cao tối thiểu có thể có mà tổng giá sách có thể có được sau khi đặt giá sách theo cách này. Vì vậy, nếu đầu vào giống như - [[1,1], [2,3], [2,3], [1,1], [1,1], [1,1], [1,2]] và self_width =4,

thì đầu ra sẽ là 6 vì tổng chiều cao của 3 giá là 1 + 3 + 2 =6. Chú ý rằng cuốn sách số 2 không phải ở giá thứ nhất.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một mảng dp có kích thước bằng sách và điền vào mảng này bằng cách sử dụng vô hạn
• dp [0]:=books [0,1]
• cho tôi trong phạm vi từ 1 đến chiều dài của sách - 1
  • curr_height:=0
  • temp:=self_width
  • j:=i
  • while j> =0 và temp - books [j, 0]> =0, do
    • curr_height:=tối đa sách [j, 1], curr_height
    • dp [i]:=min trong tổng số dp [i], curr_height + (dp [j - 1] nếu j - 1> =0, nếu không thì 0)
    • temp:=temp - books [j, 0]
    • giảm j đi 1
• trả về phần tử cuối cùng của dp

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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]

Đầu vào

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

Đầu ra

6