【算法】Filling Bookcase Shelves 填充书架-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】Filling Bookcase Shelves 填充书架。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Filling Bookcase Shelves 填充书架

问题描述：

给定一个数组 books ，其中 $b oo k s [i] = [t hi c kn ess i, h e i g h t i]$ 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。

按顺序将这些书摆放到总宽度为 shelfWidth 的书架上。

先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。

需要注意的是，在上述过程的每个步骤中，摆放书的顺序与给定图书数组 books 顺序相同。

例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。

以这种方式布置书架，返回书架整体可能的最小高度。

books.length , thickness[i],height[i] ,shelfWidth 范围[1,1000]

分析

问题本身是一个具象的书架问题，书本以数组的结构给出，而且限制必须是连续的。

也就是说要对数组划分组，每一组的要求是厚度累加不超过书架的宽度 $s h e l f w i d t h$ ，同时该层书架的高度是由这一组书中最高的高度决定的。

因为有顺序的限制，问题的难度就小了。

要求计算书架的最小高度。

如果要书架高度最小，最理想的情况，就是一层， $hi g h = ma x b oo k$ 。

但是由于width的限制，所以每一层的 $b oo k$ 数量也是由 $w i d t h$ 限制。

从0开始计算，如果 $0\rightarrow i-1$ 已经放好，此时为 $x$ 层， $x$ 层的高度为 $h 1$ ，那么 $b oo k [i]$ 就是新一层的第一本，此刻书架高度就是 $h 1 + b oo k [i] . hi g h$ 。

定义一个 $0\rightarrow i本书放完时，书架的最小高度$ 。

$b oo k [i]$ 为最后一层的第1本， $f [i] = f [i - 1] + b oo k [i] . hi g h$ ,

$b oo k [i]$ 为最后一层的第2本， $f [i] = f [i - 2] + ma x (b oo k [i] . hi g h, b oo k [i - 1] . hi g h)$ ,可以推出
$\sum_{j<=p<=i}{book[p]}<width$

代码

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1000000);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            int maxHeight = 0, curWidth = 0;
            for (int j = i; j >= 0; --j) {
                curWidth += books[j][0];
                if (curWidth > shelfWidth) {
                    break;
                }
                maxHeight = Math.max(maxHeight, books[j][1]);
                dp[i + 1] = Math.min(dp[i + 1], dp[j] + maxHeight);
            }
        }
        return dp[n];
    }
}