在M天内阅读有N章的书的最佳方式

Question

我遇到了这个采访问题:给出一本有N章的书(每章当然有不同的页数),在M天完成整本书的最佳方法是什么,约束必须完全阅读章节同一天.

例:

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

应该读一读:

Chapter1 on Day1,Chapters2 and Chapter3 on Day2, Chapter4 on Day3和Chapter5 on Day4.

我理解这个想法应该是将读取的总页数的绝对差异的总和与一天应该"理想"读取的平均页数最小化.但是,我无法将这个想法转化为数据结构和算法.任何其他想法或输入都表示赞赏.

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 - the number of pages in chapter + 1 ... chapter + add chapters).

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

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

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