我可以用二进制搜索方法解决抄书问题，因为它很容易实现。但是我刚刚开始解决动态规划问题，我想知道动态规划解决方案的问题
在印刷术发明之前，制作一本书是非常困难的一本书的副本。所有的内容都得由他手工重写称为划线器。抄写员拿到了一本书，几本书之后几个月后，他完成了副本。一位最著名的抄写员住在他的名字是泽韦里乌斯·恩德里乌斯·雷米乌斯·昂提乌斯Xendrianus(施乐)。不管怎样，那份工作很烦人，很无聊。和加快速度的唯一办法就是雇用更多的抄写员。
从前，有一个剧团想要演出著名的古代悲剧。这些剧本分为两部分当然，许多书籍和演员需要更多的副本。所以他们雇用许多抄写员抄写这些书。想象你有我书籍(编号1,2，....)， m)，可以有不同数量的Pages (p_1, p_2，…)， p_m)，您希望每个副本一个它们。你的任务是把这些书分给k个抄写员每本书只能分配给一个抄写员，而且每个抄写员抄写员必须得到连续的图书序列。这意味着存在递增数列0 = b_0
<= b_k = m$使得第i个抄写器得到一个图书序列数字在bi-1+1和bi之间。复制一份所需的时间所有的书都是由分配最多的抄写员决定的工作。因此，我们的目标是最小化最大页数分配给一个抄写员的。你的任务是找到最优的任务。
对于二分查找，我做了如下操作。
Low =1 and High = Sum of pages of all books
Run Binary search
For Mid(Max pages assigned to a scribe), assign books greedily such that no scribe gets page more than MAX
If scribes remain without work it means actual value is less than MID, if Books remain actual pages is more MID and I am updating accordingly.
这是一个用python编写的可能的动态规划解决方案。我使用从0开始的索引
k = 2 # number of scribes
# number of pages per book. 11 pages for first book, 1 for second, etc.
pages = [11, 1, 1, 10, 1, 1, 3, 3]
m = len(pages) # number of books
def find_score(assignment):
max_pages = -1
for scribe in assignment:
max_pages = max(max_pages, sum([pages[book] for book in scribe]))
return max_pages
def find_assignment(assignment, scribe, book):
if book == m:
return find_score(assignment), assignment
assign_current = [x[:] for x in assignment] # deep copy
assign_current[scribe].append(book)
current = find_assignment(assign_current, scribe, book + 1)
if scribe == k - 1:
return current
assign_next = [x[:] for x in assignment] # deep copy
assign_next[scribe + 1].append(book)
next = find_assignment(assign_next, scribe + 1, book + 1)
return min(current, next)
initial_assignment = [[] for x in range(k)]
print find_assignment(initial_assignment, 0, 0)
函数find_assignment返回赋值作为一个列表，其中第i个元素是赋给第i个抄写员的图书索引列表。作业的分数也会被返回(抄写员在作业中必须抄写的最大页数)。
动态规划的关键是首先确定子问题。在这种情况下，图书是有序的，只能按顺序分配。因此，子问题是使用s个抄写器(其中n