T******n
发帖数: 42 | 1 新人，问一道算法的作业。
Consider the problem of storing n books on shelves in a library. The
order of the books is fixed by the cataloging system and so cannot be
rearraged. Therefore, we can speak of a book bi, where 1 <= i <= n, that
has a thickness ti and height hi. The length of each bookshelf at this
library is L. Now consider the case where the height of the books is not
constant, but we have the freedom to adjust the height of each shelf to
that of the tallest book on the shelf. Thus the cost of a particular
layout is the sum of the heights of the largest book on each shelf.
(1) Give an example to show that the greedy algorithm of stuffing each
shelf as full as possible does not always give the minimum overall
height.
(2) What technique should we use to solve this problem?
(3) What are the subproblems?
(4) How many subproblems are there?
(5) Give an algorithm for this problem, and analyze its time complexity.
这个题是用dynamic programming做的。 |
|
