fai*_*gir 6 java algorithm recurrence dynamic-programming
我正在实施用于抄书问题的动态编程解决方案。解决方案的想法来自here和here。
问题陈述：
在书籍印刷发明之前，复印一本书非常困难。所有的内容都必须由所谓的抄写员手工重写。抄写员得到了一本书，几个月后他完成了副本。最著名的抄写员之一生活在 15 世纪，他的名字是 Xaverius Endricus Remius Ontius Xendrianus（施乐）。总之，工作很烦很无聊。而加快速度的唯一方法就是雇佣更多的抄写员。
曾几何时，有一个剧团想演著名的古董悲剧。这些剧本的剧本被分成了很多书，演员当然需要更多的副本。因此，他们聘请了许多抄写员来复印这些书。假设您有 m 本书（编号为 1、2、....、m），它们的页数可能不同（p_1、p_2、...、p_m），并且您想为每本书制作一份副本。你的任务是将这些书分给 k 个抄写员，k <= m。每本书只能分配给一个抄写员，并且每个抄写员都必须获得连续的书籍序列。这意味着，存在一个递增的数字序列 0 = b_0 < b_1 < b_2, ... < b_{k-1} <= b_k = m$ 使得第 i 个抄写员得到一个数字介于 bi- 1+1 和双。复印所有书籍所需的时间由分配最多工作的抄写员决定。因此，我们的目标是尽量减少分配给单个抄写员的最大页面数。您的任务是找到最佳分配。
我能够获得迭代描述的问题的最佳解决方案，但无法使用它来找到问题所需的解决方案，即：
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();
}
这里有什么指点吗？是解决方案的解释还是我在代码中翻译重复出现的方式有问题？
不确定您的解决方案，但这是一种带有记忆功能的直观递归方法。设n本书，其中第 i 本书有第[i]页。还让有m 个订阅者。如果我们只得到书i,i+1.....n并且只有j 个订阅者来完成这项工作，也让dp[i][j]成为问题的答案。以下是带有记忆功能的递归伪代码
//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
您可以通过动态编程将其转换为迭代解决方案，它将在时间和空间上具有相同的复杂度。空间为O(nm)，时间为O(n^2.m)。
编辑
这里看看您的测试用例Book Copying Code上代码的运行版本。它不仅找到最佳答案，还用它打印最佳分配（我没有将其包含在上面的伪代码中）。（点击右上角的叉子，它将在您的测试用例上运行，输入格式与您的相同）。输出将是最佳答案，然后是最佳分配。如果您对代码有疑问，请发表评论。