最佳的方式来读一本书含有的并购数N章 [英] Optimal way to read a book having N chapters in M days

问题描述

我碰到这个面试问题：假设有N个章节的书（每章都有，当然不同的页数），什么是最佳的方式与一章已成为制约完成整本书的并购天在同一天完全读

I came across this interview question: Given a book with N chapters (each chapter has of course different number of pages), what is the optimal way to complete the entire book in M days with the constraint that a chapter has to be read completely on the same day.

例如：

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

每个人都应该阅读：

One should read:

第一章对第一天， Chapters2和第3章的第2天， 第四章的第三天和第5章的第四天。

据我所知，这个想法应该是尽量减少总页数的绝对差之和阅读页面，一要理想读一天平均数量。但是，我不能这个想法转化为数据结构和算法。任何其他的想法或输入是AP preciated。

I understand that the idea should be to minimize the sum of absolute differences of total pages read with the average number of pages that one should 'ideally' read on one day. However, I am not able to translate this idea to a data structure and an algorithm. Any other idea or inputs are appreciated.

推荐答案

您可以使用动态规划。

1. 平均等于 totalNumberOfPages /在NUMBEROFDAYS ，它不依赖于我们读过书的方式。

1. The average is equal to totalNumberOfPages / numberOfDays and it does not depend on the way we read the book.

的状态是（我们已经完成的章节数，天数，我们已经花了）。一个国家的价值是绝对的差异迄今为止最小的总和。

The state is (number of chapters we have finished, the number of days we have already spent). The value of a state is the minimum sum of absolute differences so far.

基本情况，如果 F（0,0）= 0 。

转换如下：

• 假设当前状态为（章，天）。

我们可以遍历的章节数，我们将读取的第二天（我将其称为添加）并进行以下转变： F（章+添加，天+ 1）= MIN（F（章+添加，天+ 1），F（章节，天）+ ABS（平均 - 在第一章+ 1 ...章节的页数+添加章节）。

We can iterate over the number of chapters we will read the next day(I will call it add) and make the following transition: 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）。

此解决方案是基于一种假设，即我们的目标是最小化的总和页数绝对差读取与网页之一应该'理想地读在一天的平均数目。

This solution is based on an assumption that our goal is to "minimize the sum of absolute differences of total pages read with the average number of pages that one should 'ideally' read on one day".

但是，如果问题说明未说什么最优的标准是，我建议尽量减少在一天读的最大页数（在我看来，这一目标不太读多一排更有意义） 。在这种情况下，有一个更简单和有效的解决方案： 我们可以二进制搜索过的答案，并用一个贪心算法来检查，如果一个固定的候选人是可行的。

But if the problem statement does not say what the criterion of optimality is, I would suggest minimizing the maximum number of pages read during one day(in my opinion, the goal not too read to much in a row makes more sense). In this case, there is a more simple and efficient solution: we can binary search over the answer and use a greedy algorithm to check if a fixed candidate is feasible.

这篇关于最佳的方式来读一本书含有的并购数N章的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！