Copia Libri UVa Online Judge Dynamic Programing Solution

Question

Posso risolvere Copying Books Problem utilizzando il metodo di ricerca binario in quanto è facile da implementare. Ma ho appena iniziato a risolvere i problemi di dinamica programmazione e volevo sapere soluzione dinamica Programmazione per il problema

Prima dell'invenzione della libro-stampa, è stato molto difficile fare una copia di un libro. Tutti i contenuti dovevano essere riscritti a mano da chiamato scribers. Lo scriber aveva ricevuto un libro e dopo diversi anni aveva terminato la sua copia. Uno degli scrittori più famosi viveva nel XV secolo e il suo nome era Xaverius Endricus Remius Ontius Xendrianus (Xerox). Ad ogni modo, il lavoro era molto noioso e noioso. E l'unico modo per accelerare era assumere più scriber.

C'era una volta, c'era un gruppo teatrale che voleva suonare le famose tragedie antiche . Gli script di questi spettacoli erano divisi in molti libri e attori avevano bisogno di più copie di loro, naturalmente. Così loro, , assunsero molti scribers per fare copie di questi libri. Immaginate di avere m libri (numerati da 1, 2, ...., m) che possono avere diverso numero di pagine (P_1, P_2, ..., P_M) e si vuole fare una copia di ogni di loro. Il tuo compito è quello di dividere questi libri tra k scribi, k < = m. Ogni libro può essere assegnato solo a un singolo scriber e ogni scriber deve ottenere una sequenza continua di libri. Ciò significa che, non ci esiste una successione crescente di numeri 0 = b_0 < q_1 < q_2, ... < b_ {k-1} < = b_k = m $ tale che i-esimo scriber ottiene una sequenza di libri con i numeri tra bi-1 + 1 e bi. Il tempo necessario per creare una copia di di tutti i libri è determinato dallo scriber a cui è stato assegnato il maggior numero di lavori . Pertanto, il nostro obiettivo è ridurre al minimo il numero massimo di pagine assegnate a un singolo scriber. Il tuo compito è trovare l'assegnazione ottimale .

Per la ricerca binaria sto facendo quanto segue.

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

Ecco una possibile soluzione di programmazione dinamica scritta in python. Io uso l'indicizzazione a partire da 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) 

La find_assignment funzione restituisce l'incarico come una lista in cui l'elemento i-esimo è una lista di indici del libro assegnati allo scriba esimo. Viene anche restituito il punteggio del compito (il numero massimo di pagine che uno scriba deve copiare nell'assegnazione).

La chiave per la programmazione dinamica è identificare innanzitutto il sottoproblema. In questo caso, i libri sono ordinati e possono essere assegnati solo in sequenza. Pertanto, il sottoproblema consiste nel trovare un compito ottimale per gli ultimi n libri che usano gli scribi (dove n < k) e < k). Un sottoproblema può essere risolto con sottoproblemi più piccoli usando la seguente relazione: min (assegnando il libro allo scriba "corrente", assegnando il libro allo scriba successivo).