java - 背包式算法

Question

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

在发现书籍打印之前，书籍是由某些称为“作家”的人复制的。簿记员有一摞 N 本书需要复印。为此，他有 K 位作家。每本书可以有不同的页数，每个作家只能从书堆的顶部拿书(如果他拿了第一本书，那么他可以拿第二本书，但不能拿第四本书或第五本书)。簿记员知道每本书的页数，他需要在作家之间共享书籍，以使作家必须复制的最大页数尽可能少。当然，页面不能拆分你不能将一本 30 页的书分成 15 和 15 页。

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

第 1 = 145 页
第二 = 90 页
第三 = 85 页

所以这个程序是要写一个算法来找到在作者之间共享页面的最佳解决方案。所以在程序的最后你必须显示每个人得到了多少页。

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

因此，如果您愿意，请分享您的意见并提供技巧和提示，无论是数学方面的还是其他方面的，这是一个非常有趣的算法!

Answer 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