我遇到了一个访谈问题:给定一本书有N章(每章当然有不同的页数),在M天内完成一整本书的最佳方法是什么?同一天。
例:
Chapters[] = {7, 5, 3, 9, 10} Days = 4
一个应该读为:
Chapter1 on Day1,Chapters2 and Chapter3 on Day2, Chapter4 on Day3和Chapter5 on Day4。
Chapter1 on Day1
Chapters2 and Chapter3 on Day2
Chapter4 on Day3
Chapter5 on Day4
我了解该想法应该是将一天中应该“理想地”阅读的平均页面数与阅读的总页面数的绝对差之和减到最小。但是,我无法将此想法转换为数据结构和算法。任何其他想法或意见表示赞赏。
您可以使用动态编程。
平均值等于totalNumberOfPages / numberOfDays并且不取决于我们阅读本书的方式。
totalNumberOfPages / numberOfDays
状态为(我们完成的章节数量,已经使用的天数)。状态的值是到目前为止的绝对差的最小和。
基本情况是f(0, 0) = 0。
f(0, 0) = 0
转换如下:
假设当前状态为(chapters, days)。
(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).
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).
答案是f(totalNumberOfChapters, totalNumberOfDays)。
f(totalNumberOfChapters, totalNumberOfDays)
该解决方案基于以下假设:我们的目标是“将每天阅读的总页数的绝对差异的总和与一个人每天应该理想地阅读的平均页数相减”。
但是,如果问题陈述没有说出最佳标准是什么,我建议尽量减少一天内的最大读取页数(我认为,目标不是连续读取过多会更有意义)。在这种情况下,有一个更简单有效的解决方案:我们可以对答案进行二进制搜索,然后使用贪心算法来检查固定的候选对象是否可行。