用 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

