algorithm - 在 M 天内阅读一本有 N 章的书的最佳方式

Question

我遇到了这个面试问题:给定一本有 N 章的书(每一章当然有不同的页数)，在 M 天内完成整本书的最佳方法是什么在同一天完整阅读。

示例:

Chapters[] = {7, 5, 3, 9, 10}
Days = 4

应该阅读:

第 1 天的第 1 章，第 2 天的第 2 章和第 3 章， 第 3 天的第 4 章和第 4 天的第 5 章。

我理解这个想法应该是最小化阅读总页数与一天“理想”阅读的平均页数的绝对差之和。但是，我无法将这个想法转化为数据结构和算法。感谢任何其他想法或意见。

Answer 1

你可以使用动态规划。

1. 平均值等于 totalNumberOfPages/numberOfDays，它与我们阅读本书的方式无关。

2. 状态是(我们完成的章节数，我们已经度过的天数)。一个状态的值是到目前为止的绝对差的最小和。

3. f(0, 0) = 0 的基本情况。

4. 过渡如下:

   • 假设当前状态是(chapters, days)。

   • 我们可以遍历第二天要阅读的章节数(我称之为add)并进行以下转换:f(chapters + add, days + 1) = min(f(chapters + add, days + 1), f(chapters, days) + abs(average - chapter 的页数 + 1 ... chapter + add chapters).

5. 答案是f(totalNumberOfChapters, totalNumberOfDays)。

此解决方案基于这样一个假设，即我们的目标是“将阅读的总页数与一天应该‘理想’阅读的平均页数的绝对差之和最小化”。

但如果问题陈述没有说明最优性标准是什么，我建议尽量减少一天内阅读的最大页数(在我看来，目标不要连续阅读太多更有意义) .对于这种情况，有一个更简单高效的解决方案: 我们可以对答案进行二分搜索，并使用贪心算法来检查固定候选是否可行。