复制书籍弗吉尼亚大学在线评测动态规划解决方案 [英] Copying Books UVa Online Judge Dynamic Programing Solution

问题描述

我可以解决<一个href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=655"相对=nofollow>复制书籍的问题使用二进制搜索方法，因为它很容易实现。不过我刚开始解决动态规划问题，我想知道的问题，动态规划解决方案

  

书印刷术发明之前，人们很难做出   一本书的副本。所有的内容必须被重新写入由手通过这样   所谓划线。划片已获得一本书，并经过多次   个月，他完成了它的副本。其中最有名的划线住在   15世纪，他的名字是Xaverius Endricus Remius Ontius   Xendrianus（施乐）。总之，这项工作是非常讨厌和乏味。和   要加快它的唯一方法是雇用更多的划线。

     

很久很久以前，有说想打一个剧院乐团   著名的古董悲剧。这些戏剧的剧本分成   许多书籍和演员需要更多的副本当中，当然。所以他们   聘请了很多划线，使这些书的副本。想象一下，你有m个   书籍的（编号为1，2，...，米），其可具有不同数量的的   网页的（P_1，P_2，...，p_m）的，你想使每一个副本   对他们。你的任务是把这些书ķ文士之间，K＆LT; =   米每本书可以被分配到只有一个单一的划刻器，和每   划线必须把书的连续序列。这意味着，有   存在数的增加连续0 = B_0＆其中; B_1＆LT; B_2，...   ＆LT; B_ {k-1}＆LT; = b_k = M $使得第i个划线得到的书籍序列   用双1 + 1和双之间的数字。所需要的时间，使副本   所有的书是由谁是最分配划线确定   工作。因此，我们的目标是尽量减少页面的最大数量   分配给单个划线。你的任务是找到最佳   分配。

有关二进制搜索我做了以下内容。

 低= 1的所有的书页和高= SUM

 运行二进制搜索

 对于MID（分配到一个文士最大页），指定的书籍贪婪使得没有划线变得页面超过MAX

 如果文士仍然没有工作，这意味着实际值小于MID，如果书籍保持实际的页面更MID和我更新相应地。
 

解决方案

下面是用Python编写的一个可能的动态编程解决方案。我使用索引从0开始。

  K = 2＃号文士
＃每本书的页数。 11页的第一本书，1秒，等等。
页= [11，1，1，10，1，1，3，3]
M = len个（页）＃数量的书籍


高清find_score（分配）：
    MAX_PAGES = -1
    为隶在分配：
        MAX_PAGES = MAX（MAX_PAGES，SUM（[页[图书]的书隶））
    返回MAX_PAGES


高清find_assignment（分配，隶，书）：
    如果书== M：
        返回find_score（分配），分配
    assign_current = [X [：]对于x在分配]＃深拷贝
    assign_current [抄写员] .append（书）
    电流= find_assignment（assign_current，隶，书+ 1）
    如果划线==的K  -  1：
        返回电流
    assign_next = [X [：]对于x在分配]＃深拷贝
    assign_next [隶+ 1] .append（书）
    接下来= find_assignment（assign_next，隶+ 1，书+ 1）
    返回分钟（目前，下一个）


initial_assignment = [[] x的范围（k）的]
打印find_assignment（initial_assignment，0，0）
 

find_assignment返回分配作为一个列表，其中第i个元素是分配给第i个刻划书索引的列表的功能。分配的得分被返回，以及（最大页数的划线具有在分配复制）。

的关键，动态规划是先找出子问题。在这种情况下，书是有序的，并且只能按顺序分配。因此，子问题是找到对于使用的书记最后n书籍的最佳分配（其中n＆所述; m和s＆其中; K）。子问题可以解决，使用下面的关系较小的子问题：最小（指定书当前划片，分配到本书的下隶）

I can solve Copying Books Problem using binary search method as it is easy to implement. But I have just started solving Dynamic Programing problems and I wanted to know Dynamic Programing solution for the 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.

For Binary Search I am doing the following.

 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.

解决方案

Here is a possible dynamic programming solution written in python. I use indexing starting from 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)

The function find_assignment returns the assignment as a list where the ith element is a list of book indexes assigned to the ith scribe. The score of the assignment is returned as well (the max number of pages a scribe has to copy in the assignment).

The key to dynamic programming is to first identify the subproblem. In this case, the books are ordered and can only be assigned sequentially. Thus the subproblem is to find an optimal assignment for the last n books using s scribes (where n < m and s < k). A subproblem can be solved with smaller subproblems using the following relation: min(assigning book to the "current" scribe, assigning the book to the next scribe).

这篇关于复制书籍弗吉尼亚大学在线评测动态规划解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！