1105. Filling Bookcase Shelves [Dynamic Programming]
Goal¶
This post aims to describe the solution for 1105. Filling Bookcase Shelves based on the solution by a respectful coder Hexadecimal. This problem could be solved by dynamic programming.
Problem¶
We have a sequence of books: the i-th book has thickness books[i][0] and height books[i][1].
We want to place these books in order onto bookcase shelves that have total width shelf_width.
We choose some of the books to place on this shelf (such that the sum of their thickness is <= shelf_width), then build another level of shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.
Note again that at each step of the above process, the order of the books we place is the same order as the given sequence of books. For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.
Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.
Example 1:¶
Input:
books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]],
shelf_width = 4
Output: 6
Explanation: The sum of the heights of the 3 shelves are 1 + 3 + 2 = 6. Notice that book number 2 does not have to be on the first shelf.
Solution by Hexadecimal¶
This problem is solved by dynamic programming. Considering the scenarios from 1 book to n books by adding one book at a time, we can leverage the result from the previous result. For example, when we know the minimum height of the shelf is 8 and are going to place another book, we only need to try two things:
- try to place this book on the same row
- if it is not feasible, we need to place on the next level
- if it is feasible,
- place the book on the same level,
- update the maximum height at the same level, and
- keep the case for achieving the minimum height
This way only consider the best case scenario in the previous case, and take that case as the starting point.
Original Solution¶
Line by line breakdown are as follows:
- Initial setting
-
n: a number of books -
dp: keep and track the minimum height of book shelf when we place a book one by one. This is initialized byinfinity. The last elementdp[-1]will be the answer that we look for.
-
- Consider the scenarios by adding one book at a time.
-
i: the hypothetical number of the books. Given this number of the book, we will calculate the minimum height of the books. Adding the book to consider one by one, we can leverage the result fori-1books case for the one foribooks case. -
width: the total width for the placed book on the same level. Whenwidthis beyondw, the width of the shelf,widthwill be reset to0. -
h: the maximum height for each level. -
j: the book to place given thei+1books.jis selected from the end to the start in a reverse order.
-
from typing import List
class Solution:
def minHeightShelves(self, b: List[List[int]], w: int) -> int:
n = len(b)
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(n):
j = i
width = 0
h = 0
while j >= 0:
width += b[j][0]
if width > w:
break
h = max(h, b[j][1])
dp[i + 1] = min(dp[i + 1], dp[j] + h)
j -= 1
return dp[-1]
Modified Solution with print¶
from typing import List
class Solution:
def minHeightShelves(self, b: List[List[int]], w: int) -> int:
print(f'Books: {b}\nShelf width: {w}')
n = len(b)
dp = [float('inf')] * (n + 1)
dp[0] = 0
print(f'initial dp: {dp}')
for i in range(n):
print()
print('-' * 80)
print(f'[{i+1} books] to consider: {b[:i+1]}')
j = i
width = 0
h = 0
while j >= 0:
print(f'place [{j}]-th book: {b[j]}')
width += b[j][0]
if width > w:
print('The total width is beyond the shelf')
break
print(f'The maximum height is updated from [{h}] to [{max(h, b[j][1])}]')
h = max(h, b[j][1])
print(f'The minimum total height for [{i+1} books] is update from [{dp[i + 1]}] to [{min(dp[i + 1], dp[j] + h)}]')
dp[i + 1] = min(dp[i + 1], dp[j] + h)
j -= 1
return dp[-1]
Test case 1¶
books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]; shelf_width = 4
s = Solution()
s.minHeightShelves(books, shelf_width)
Test case 2¶
books = [[7,3],[8,7],[2,7],[2,5]]; shelf_width = 10
s = Solution()
s.minHeightShelves(books, shelf_width)
Comments
Comments powered by Disqus