用 Python 填充书柜书架

pythonserver side programmingprogramming更新于 2025/8/25 10:20:17

假设我们有一系列书籍 − 这里第 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]],并且 self_width = 4,

那么输出将是 6,因为 3 个架子的高度之和为 1 + 3 + 2 = 6。请注意,2 号书不一定在第一个架子上。

要解决这个问题,我们将遵循以下步骤 −

  • 创建一个大小与书籍相同的数组 dp,并使用无限填充它
  • dp[0] := books[0,1]
  • for i in range 1 to length of books – 1
    • curr_height := 0
    • temp := self_width
    • j := i
    • while j >= 0 and temp – books[j, 0] >= 0, do
      • curr_height := books[j, 1] 的最大值,curr_height
      • dp[i] := dp[i] 的最小值,curr_height + (dp[j - 1] if 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

相关文章


有用资源