一个人下定决心要在“k”天内完成这本书，但他从来不想在这两天之间停下一章。找到最佳的章节分配，这样这个人就不会阅读太多额外/更少的页面。
null
例子：
Input: Number of Days to Finish book = 2
Number of pages in chapters = {10, 5, 5}
Output: Day 1: Chapter 1
Day 2: Chapters 2 and 3
Input: Number of Days to Finish book = 3
Number of pages in chapters = {8, 5, 6, 12}
Output: Day 1: Chapter 1
Day 2: Chapters 2 and 3
Day 2: Chapter 4
目标是将每天阅读的页面与平均页数之间的差异之和降至最低。如果平均页数为非整数，则应将其四舍五入为最接近的整数。
在上面的示例2中，平均页数为（8+5+6+12）/3=31/3，四舍五入为10。因此，对于上面显示的输出，每天的平均页数和页数之间的差异是“abs（8-10）+abs（5+6-10）+abs（12-10）”，即5。值5是差和的最佳值。
考虑上面的例子2，其中一本书有4章，第8, 5, 6页和第12页。用户希望在3天内完成。上述场景的图形表示为：，
在上图中，顶点代表章节，边e（u，v）代表从“u”读到“v”的页数。增加了Sink节点，表示书的结尾。
首先，计算一天平均要阅读的页数（这里是31/3，大约10页）。新的边权重e’（u，v）将是平均差| avg–e（u，v）|。上述问题的修正图是，
幸亏 犰狳 感谢你在评论中提出这个想法。
我们的想法是从第1章开始，做一个DFS来查找边数为“k”的水槽。继续将访问的顶点存储在一个数组中，比如“路径[]”。如果我们到达目标顶点，且路径和小于最优路径，则更新最优分配最优_路径[]。请注意，图表是DAG，因此在DFS期间不需要考虑周期。 下面是C++实现的相同，邻接矩阵是用来表示图的。以下项目主要分为4个阶段。 1） 构造一个有向无环图。 2） 使用DFS找到最佳路径。 3） 打印找到的最佳路径。
C++
// C++ DFS solution to schedule chapters for reading in // given days # include <iostream> # include <cstdlib> # include <climits> # include <cmath> using namespace std; // Define total chapters in the book // Number of days user can spend on reading # define CHAPTERS 4 # define DAYS 3 # define NOLINK -1 // Array to store the final balanced schedule int optimal_path[DAYS+1]; // Graph - Node chapter+1 is the sink described in the // above graph int DAG[CHAPTERS+1][CHAPTERS+1]; // Updates the optimal assignment with current assignment void updateAssignment( int * path, int path_len); // A DFS based recursive function to store the optimal path // in path[] of size path_len. The variable sum stores sum of // of all edges on current path. k is number of days spent so // far. void assignChapters( int u, int * path, int path_len, int sum, int k) { static int min = INT_MAX; // Ignore the assignment which requires more than required days if (k < 0) return ; // Current assignment of chapters to days path[path_len] = u; path_len++; // Update the optimal assignment if necessary if (k == 0 && u == CHAPTERS) { if (sum < min) { updateAssignment(path, path_len); min = sum; } } // DFS - Depth First Search for sink for ( int v = u+1; v <= CHAPTERS; v++) { sum += DAG[u][v]; assignChapters(v, path, path_len, sum, k-1); sum -= DAG[u][v]; } } // This function finds and prints optimal read list. It first creates a // graph, then calls assignChapters(). void minAssignment( int pages[]) { // 1) ............CONSTRUCT GRAPH................. // Partial sum array construction S[i] = total pages // till ith chapter int avg_pages = 0, sum = 0, S[CHAPTERS+1], path[DAYS+1]; S[0] = 0; for ( int i = 0; i < CHAPTERS; i++) { sum += pages[i]; S[i+1] = sum; } // Average pages to be read in a day avg_pages = round(sum/DAYS); /* DAG construction vertices being chapter name & * Edge weight being |avg_pages - pages in a chapter| * Adjacency matrix representation */ for ( int i = 0; i <= CHAPTERS; i++) { for ( int j = 0; j <= CHAPTERS; j++) { if (j <= i) DAG[i][j] = NOLINK; else { sum = abs (avg_pages - (S[j] - S[i])); DAG[i][j] = sum; } } } // 2) ............FIND OPTIMAL PATH................ assignChapters(0, path, 0, 0, DAYS); // 3) ..PRINT OPTIMAL READ LIST USING OPTIMAL PATH.... cout << "Optimal Chapter Assignment :" << endl; int ch; for ( int i = 0; i < DAYS; i++) { ch = optimal_path[i]; cout << "Day" << i+1 << ": " << ch << " " ; ch++; while ( (i < DAYS-1 && ch < optimal_path[i+1]) || (i == DAYS-1 && ch <= CHAPTERS)) { cout << ch << " " ; ch++; } cout << endl; } } // This function updates optimal_path[] void updateAssignment( int * path, int path_len) { for ( int i = 0; i < path_len; i++) optimal_path[i] = path[i] + 1; } // Driver program to test the schedule int main( void ) { int pages[CHAPTERS] = {7, 5, 6, 12}; // Get read list for given days minAssignment(pages); return 0; } |
Python3
# Python3 DFS solution to schedule chapters # for reading in given days # A DFS based recursive function to store # the optimal path in path[] of size path_len. # The variable Sum stores Sum of all edges on # current path. k is number of days spent so far. def assignChapters(u, path, path_len, Sum , k): global CHAPTERS, DAYS, NOLINK, optical_path, DAG, Min # Ignore the assignment which requires # more than required days if (k < 0 ): return # Current assignment of chapters to days path[path_len] = u path_len + = 1 # Update the optimal assignment if necessary if (k = = 0 and u = = CHAPTERS): if ( Sum < Min ): updateAssignment(path, path_len) Min = Sum # DFS - Depth First Search for sink for v in range (u + 1 , CHAPTERS + 1 ): Sum + = DAG[u][v] assignChapters(v, path, path_len, Sum , k - 1 ) Sum - = DAG[u][v] # This function finds and prints # optimal read list. It first creates a # graph, then calls assignChapters(). def MinAssignment(pages): global CHAPTERS, DAYS, NOLINK, optical_path, DAG, MIN # 1) ............CONSTRUCT GRAPH................. # Partial Sum array construction S[i] = total pages # till ith chapter avg_pages = 0 Sum = 0 S = [ None ] * (CHAPTERS + 1 ) path = [ None ] * (DAYS + 1 ) S[ 0 ] = 0 for i in range (CHAPTERS): Sum + = pages[i] S[i + 1 ] = Sum # Average pages to be read in a day avg_pages = round ( Sum / DAYS) # DAG construction vertices being chapter name & # Edge weight being |avg_pages - pages in a chapter| # Adjacency matrix representation for i in range (CHAPTERS + 1 ): for j in range (CHAPTERS + 1 ): if (j < = i): DAG[i][j] = NOLINK else : Sum = abs (avg_pages - (S[j] - S[i])) DAG[i][j] = Sum # 2) ............FIND OPTIMAL PATH................ assignChapters( 0 , path, 0 , 0 , DAYS) # 3) ..PROPTIMAL READ LIST USING OPTIMAL PATH.... print ( "Optimal Chapter Assignment :" ) ch = None for i in range (DAYS): ch = optimal_path[i] print ( "Day" , i + 1 , ": " , ch, end = " " ) ch + = 1 while ((i < DAYS - 1 and ch < optimal_path[i + 1 ]) or (i = = DAYS - 1 and ch < = CHAPTERS)): print (ch, end = " " ) ch + = 1 print () # This function updates optimal_path[] def updateAssignment(path, path_len): for i in range (path_len): optimal_path[i] = path[i] + 1 # Driver Code # Define total chapters in the book # Number of days user can spend on reading CHAPTERS = 4 DAYS = 3 NOLINK = - 1 # Array to store the final balanced schedule optimal_path = [ None ] * (DAYS + 1 ) # Graph - Node chapter+1 is the sink # described in the above graph DAG = [[ None ] * (CHAPTERS + 1 ) for i in range (CHAPTERS + 1 )] Min = 999999999999 pages = [ 7 , 5 , 6 , 12 ] # Get read list for given days MinAssignment(pages) # This code is contributed by PranchalK |
输出：
Optimal Chapter Assignment : Day1: 1 Day2: 2 3 Day3: 4
本文由 巴拉吉S 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
