0

这是我发现的一个非常有趣的 java 问题：

在发现书籍印刷之前，书籍是由某些称为“作家”的人复制的。簿记员有一叠 N 本书需要复制。为此，他有 K 个作家。每本书可以有不同的页数，每个作者只能从堆栈顶部取书（如果他取书 1，那么他可以取书 2，但不能取书 4 或书 5）。簿记员知道每本书的页数，他需要在作者之间共享书籍，以使作者必须复制的最大页数尽可能少。例如，当然不能拆分页面你不能把一本 30 页的书分成 15 页和 15 页。

例如，如果我们有 7 本书，有 3 位作者，并且相应的书籍页数为：30 50 5 60 90 5 80，那么最佳解决方案是第一个作者拿前 4 本书，第二位作者拿下本书，第三位拿下本书。最后两本书，所以我们会有：

第 1 = 145 页
第 2 = 90 页
第 3 = 85 页

所以程序是编写一个算法来找到在作者之间共享页面的最佳解决方案。因此，在程序结束时，您必须显示每个人获得了多少页。

这是几年前的一次编程比赛，我想试一试，到目前为止我发现如果你把所有书籍的总页数除以你在例如 106.66 页，然后您尝试将堆栈中最接近该数字的连续书籍提供给每个作者，但这对于大页码根本不起作用，特别是如果一本书的页数超过总页数页数除以作者数

因此，如果您愿意，请分享您的意见并提供提示和提示，数学或其他，这是一个非常有趣的算法！

4

4 回答 4

1

让我们假设您有书 1...n，页面为 b1,b2,...,bn。假设你有 K 个作家。

初始化一个矩阵 F[1...n,1...K]=infinity。

令 F[i,1]= sum_j=1..i (bj)

现在，对于每 k=2..K

F[i,k] = min_j=1..i( max(F[j,k-1], sum_r=j+1..i (br) )

于 2012-04-28T18:06:47.603 回答
1

我想出了一个直截了当的解决方案，可能效率不高，但逻辑有效。基本上你从作家的数量开始与书籍的数量相同，然后减少直到你有你的作家数量。

举个例子。假设你从你的七个值开始，30 50 5 60 90 5 80。对于每一步，你通过总结“最低对”来减少一个。粗体的值是进行到下一次迭代的对。

7
30 50 5 60 90 5 80
6
30 55 60 90 5 80
5
30 55 60 90 85
4
85 60 90 85
3
145 90 85

通过一些伪编程，这个例子展示了它是如何实现的

main(books: { 30 50 5 60 90 5 80 }, K: 3)

define main(books, K)
  writers = books
  while writers.length > K do
    reduceMinimalPair(writers)
  endwhile
end

define reduceMinimalPair(items)
  index = 0
  minvalue = items[0] + items[1]
  for i in 1..items.length-1 do
    if items[i] + items[i + 1] < minvalue then
      index = i
      minvalue = items[i] + items[i + 1]
    endif
  endfor
  items.removeat(index)
  items.removeat(index + 1)
  items.insertat(index, minvalue)
end
于 2012-04-28T20:08:39.287 回答
0

我认为您认为的方式是正确的，但是如果您说它不适用于大数字，那么也许您应该检查是否存在比平均值更大的数字并在这种情况下做其他事情。也许删除数字并从一开始就将其提供给作家或类似的东西

于 2012-04-28T17:56:47.167 回答
0

除了使用动态编程解决它之外，您还可以二进制搜索每个人都不会复制超过此页数的页数上限。当这个数字收敛时，这就是答案。

于 2012-04-28T18:54:10.777 回答