使用动态规划复制书籍

Question

我正在实现复印书籍问题的动态规划解决方案。解决方案的想法来自 here and here.

问题陈述：

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.

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 <= 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 < b_1 < b_2, ... < b_{k-1} <= 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.

我能够得到迭代描述的问题的最优解，但无法用它来找到问题所需的解，即：

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

其中 2 是数据集的数量，9 是书籍的数量，3 是分配书籍的抄写员的数量。

这是我的输出，针对相应的输入：

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

对于第一个解决方案集，我可以使用 1700 作为分配给每个用户的最佳页数，并继续分配书页，直到当前抄写页总和 >= 1700。但是，第二个解决方案没有有什么模式吗？

这是我生成解决方案的代码：

private void processScribes(){
        int[][] bookScribe = new int[numOfBooks][numOfScribes];
        //set first row to b1 page number
        for (int j = 0; j < numOfScribes; ++j)
            bookScribe[0][j] = bookPages[0];

        //set first column to sum of book page numbers
        for (int row = 1; row < numOfBooks; ++row)
            bookScribe[row][0] = bookScribe[row - 1][0] + bookPages[row]; 

        //calculate the kth scribe using dp
        for (int i = 1; i < numOfBooks; ++i){
            for (int j = 1; j < numOfScribes; ++j){
                //calculate minimum of maximum page numbers
                //from k = l + 1 to i
                //calculate sum 
                int minValue = 1000000;
                for (int k = 0; k < i - 1; ++k){
                    int prevValue = bookScribe[i - k][j - 1];
                    int max = 0;
                    int sumOflVals = 0;
                    for (int l = k + 1; l <= i; ++l){
                        sumOflVals = sumOflVals + bookPages[l];
                    }
                    if (prevValue > sumOflVals){
                        max = prevValue;
                    }
                    else
                        max = sumOflVals;
                    if (max < 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 < numOfBooks; ++i){
            for (int j = 0; j < numOfScribes; ++j)
                System.out.print(bookScribe[i][j] + " ");
            System.out.println();
        }
        System.out.println();
    }

这里有任何指示吗？是解决方案的解释还是我在代码中翻译循环的方式有问题？

Answer 1

不确定您的解决方案，但这是一种带有记忆的直观递归方法。假设有 n 本书，其中第 i 本书有 pages[i] 页。还要有 m 个订阅者。如果我们只给了书 dp[i][j] 也让 dp[i][j] 成为问题的答案 i,i+1.....n 并且只有 j 个订阅者可以完成这项工作。以下是带有 memoization

的递归伪代码

    //dp[][] is memset to -1 from main
    // Assuming books are numbered 1 to n
    // change value of MAX based on your constraints
    int MAX = 1000000000;
    int rec(int position , int sub )
    {
          // These two are the base cases
          if(position > n)
          {
             if(sub == 0)return 0;
             return MAX;
          }
          if(sub == 0)
          {
              if(position > n)return 0;
              return MAX;
          }

          // If answer is already computed for this state return it
          if(dp[position][sub] != -1)return dp[position][sub];

          int ans = MAX,i,sum = 0;
          for(i = position; i <= n;i++)
          {
             sum += pages[i];
             // taking the best of all possible solutions
             ans = min(ans,max(sum,rec(i+1,sub-1)));
          }
          dp[position][sub]=ans;
          return ans; 
    }

    //from main call rec(1,m) which is your answer

您可以通过动态规划将其转换为迭代解决方案，它在时间上具有相同的复杂性并且 space .Space 是 O(n.m) 时间是 O(n^2.m).

编辑
在这里查看测试用例运行ning 版本的代码 Book Copying Code 。它不仅找到了最佳答案，而且还打印了最佳分配（我没有包含在上面的伪代码中）。（点击右上角的叉子，它会运行您的测试用例，输入格式与您的相同）。输出将是最佳答案，然后是最佳分配。如果您对代码有疑问，请发表评论。

使用动态规划复制书籍

Copying books using dynamic programming

java

algorithm

dynamic-programming

recurrence