title: Copying books using dynamic programming
body: <p>I am implementing the dynamic programming solution for copying books problem. The idea for the solution is taken from <a href="http://www.csie.ntu.edu.tw/~hsinmu/courses/_media/ada_13fall/midterm2013_sol.pdf" rel="nofollow noreferrer">here</a> and <a href="https://stackoverflow.com/questions/23680188/copying-books-uva-online-judge-dynamic-programing-solution">here</a>.</p>
  
  <p>Problem statement:</p>
  
  <blockquote>
    <p>Before the invention of book-printing, it was very hard to make a copy
    of a book. All the contents had to be re-written by hand by so called
    scribers. The scriber had been given a book and after several months
    he finished its copy. One of the most famous scribers lived in the
    15th century and his name was Xaverius Endricus Remius Ontius
    Xendrianus (Xerox). Anyway, the work was very annoying and boring. And
    the only way to speed it up was to hire more scribers.</p>
    
    <p>Once upon a time, there was a theater ensemble that wanted to play
    famous Antique Tragedies. The scripts of these plays were divided into
    many books and actors needed more copies of them, of course. So they
    hired many scribers to make copies of these books. Imagine you have m
    books (numbered 1, 2, ...., m) that may have different number of pages
    ( p_1, p_2, ..., p_m) and you want to make one copy of each of them.
    Your task is to divide these books among k scribes, k &lt;= m. Each book
    can be assigned to a single scriber only, and every scriber must get a
    continuous sequence of books. That means, there exists an increasing
    succession of numbers 0 = b_0 &lt; b_1 &lt; b_2, ... &lt; b_{k-1} &lt;= b_k = m$
    such that i-th scriber gets a sequence of books with numbers between
    bi-1+1 and bi. The time needed to make a copy of all the books is
    determined by the scriber who was assigned the most work. Therefore,
    our goal is to minimize the maximum number of pages assigned to a
    single scriber. Your task is to find the optimal assignment.</p>
  </blockquote>
  
  <p>I am able to obtain the optimal solution for the problem described iteratively, but unable to use that to find the required solution for the problem, that is:</p>
  
  <pre><code>Sample input:
  2
  9 3
  100 200 300 400 500 600 700 800 900
  5 4
  100 100 100 100 100
  
  Sample Output
  100 200 300 400 500 / 600 700 / 800 900
  100 / 100 / 100 / 100 100
  </code></pre>
  
  <p>Where 2 is the number of datasets, 9 is the number of books and 3 is the number of scribes to assign the books to.</p>
  
  <p>Here is my output, for the respective inputs:</p>
  
  <pre><code>100 100 100 
  300 300 300 
  600 600 600 
  1000 700 700 
  1500 900 900 
  2100 1100 1100 
  2800 1300 1300 
  3600 1500 1500 
  4500 1700 1700 
  
  100 100 100 100 
  200 200 200 200 
  300 300 300 300 
  400 300 300 300 
  500 300 300 300 
  </code></pre>
  
  <p>For the first solution set, I can use 1700 as the optimal number of page assignments to each user and keep on assigning the book pages until, Current scribe page sum >= 1700. However, the second solution does not have any pattern to it whatsoever?</p>
  
  <p>Here is my code to generate the solution:</p>
  
  <pre><code>private void processScribes(){
          int[][] bookScribe = new int[numOfBooks][numOfScribes];
          //set first row to b1 page number
          for (int j = 0; j &lt; numOfScribes; ++j)
              bookScribe[0][j] = bookPages[0];
  
          //set first column to sum of book page numbers
          for (int row = 1; row &lt; numOfBooks; ++row)
              bookScribe[row][0] = bookScribe[row - 1][0] + bookPages[row]; 
  
          //calculate the kth scribe using dp
          for (int i = 1; i &lt; numOfBooks; ++i){
              for (int j = 1; j &lt; numOfScribes; ++j){
                  //calculate minimum of maximum page numbers
                  //from k = l + 1 to i
                  //calculate sum 
                  int minValue = 1000000;
                  for (int k = 0; k &lt; i - 1; ++k){
                      int prevValue = bookScribe[i - k][j - 1];
                      int max = 0;
                      int sumOflVals = 0;
                      for (int l = k + 1; l &lt;= i; ++l){
                          sumOflVals = sumOflVals + bookPages[l];
                      }
                      if (prevValue &gt; sumOflVals){
                          max = prevValue;
                      }
                      else
                          max = sumOflVals;
                      if (max &lt; minValue )
                          minValue = max;
                  }
                  if (minValue == 1000000)
                      minValue = bookScribe[i][0];
                  //store minvalue at [i][j]
                  bookScribe[i][j] = minValue;
              }
          }
  
          //print bookScribes
          for (int i = 0; i &lt; numOfBooks; ++i){
              for (int j = 0; j &lt; numOfScribes; ++j)
                  System.out.print(bookScribe[i][j] + " ");
              System.out.println();
          }
          System.out.println();
      }
  </code></pre>
  
  <p>Any pointers here? Is it the interpretation of solution or something is wrong with how I am translating the recurrence in my code?</p>