复制书籍UVa在线评判动态编程解决方案

Question

我可以使用二进制搜索方法解决复制书籍问题,因为它易于实现.但我刚刚开始解决动态编程问题,我想知道问题的动态编程解决方案

在书籍印刷术发明之前,制作一本书的副本非常困难.所有的内容都必须由所谓的划线员手工重写.划线员得到了一本书,几个月后他完成了复印件.其中一位最着名的抄写员生活在15世纪,他的名字是Xaverius Endricus Remius Ontius Xendrianus(Xerox).无论如何,这项工作非常烦人和无聊.加快速度的唯一方法就是雇佣更多的抄写员.

曾几何时,有一个剧院合奏,想要演奏着名的古董悲剧.当然,这些剧本的剧本分为许多书,演员需要更多的副本.所以他们聘请了许多抄写员来复制这些书.想象一下,你有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 $,这样我的抄写员就可以得到一系列数字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.

Answer 1

这是一个用 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 < m 且 s < k）找到最后 n 本书的最佳分配。可以使用以下关系用较小的子问题来解决子问题：min（将书分配给“当前”抄写员，将书分配给下一个抄写员）。