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

Question

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

示例:

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

应该阅读:

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

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

Answer 1

您可以使用动态规划。

1. 平均值等于totalNumberOfPages/numberOfDays，并且不取决于我们阅读书籍的方式。

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

3. 基本情况，如果 f(0, 0) = 0。

4. 转换如下:

   • 假设当前状态是(章节，天数)。

   • 我们可以迭代第二天要阅读的章节数(我将其称为 add)并进行以下转换:f(chapters + add, days + 1) = min(f(章节数 + 添加, 天数 + 1), f(章节数, 天数) + abs(平均值 - 章节页数 + 1 ... 章节 + 添加章节)。

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

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

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