algorithm - 抄书 UVa Online Judge 动态规划解决方案

Question

我可以解决Copying Books Problem使用二进制搜索方法，因为它很容易实现。但是我刚刚开始解决动态规划问题，我想知道该问题的动态规划解决方案

Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.

Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2, ...., m) that may have different number of pages ( p_1, p_2, ..., p_m) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b_0 < b_1 < b_2, ... < b_{k-1} <= b_k = m$ such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

对于二进制搜索，我正在执行以下操作。

 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(将书分配给“当前”抄写员，将书分配给下一个抄写员)。