Informally in this problem we consider how to divide the chapters in a story int
ID: 3819345 • Letter: I
Question
Informally in this problem we consider how to divide the chapters in a story into volumes (think the seven volumes of Harry Potter or however many Game of Thrones volumes there will be) so as to equalize the size of the volumes. The input consists of positive integers x_1, x_2,...,x_n and k lessthanorequalto n. Here x_i is the number of pages in chapter i, and k is the desired number of volumes. The problem is determine which chapters go into each of the k volumes so as to minimize the difference between the most number of pages in any volumes, and the least number of pages in any of the volumes. Of course you cannot reorder the story. Give an algorithm whose running time is bounded by a polynomial in n. You running time should not depend on the number of pages in the chapters.Explanation / Answer
Applying dynamic programming:
We shall use the dynamic-programming method to determine how to optimally
divide this into concrete solution. We must remember this sequence:
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution.
4. Construct an optimal solution from computed information.
We can simulate it with the rod cutting problem we have studied. we have a long rod/a long chapter, and we have to divide it.
For each i, we have xi with us.
We can use the TOp DOwn Approach but there each subproblem is repeatedly and recursively solved.
So , lets instead use the bottom up approach to do it:
Here p is an array of our x[i]. and n is our total
BOTTOM-UP-DIVIDE-VOLUME(p,n)
1 let r 0:n be a new array
2 r[0]=0
3 for j = 1 to n
4 q = -inf
5 for i = 1 to j
6 q =max(q,p[i]+r[j-i]);
7 r[j]=q;
8 return r[n]