Re: [閒聊] 每日leetcode

[smart0eddie (smart0eddie)]

2024-07-31
1105. Filling Bookcase Shelves
You are given an array books where books[i] = [thicknessi, heighti] indicates
the thickness and height of the ith book. You are also given an integer
shelfWidth.

We want to place these books in order onto bookcase shelves that have a total
width shelfWidth.

We choose some of the books to place on this shelf such that the sum of their
thickness is less than or equal to shelfWidth, then build another level of
the 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 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.

那張圖看起來就是 scheduling
看起來大概就是 dynamic programming
可能是要根據目前為止前k本的最佳解決定k+1本是要加一層還是塞進前一層
然後
(打開解答抄)

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722403090.A.CE0.html
推 DJYOMIYAHINA: 早上打開電腦的我：嗯嗯greddy出發 然後WA 就這樣
→ DJYOMIYAHINA: 了
→ DJYOMIYAHINA: *greedy
→ smart0eddie: greedy 可以嗎
推 oin1104: greedy不行
→ oin1104: 我好恨
→ smart0eddie: greedy 的話例題第一題的第二本會塞進第一層欸
→ smart0eddie: 然後很肥的第三本就只能開第二層