पुस्तकें कॉपी करना यूवीए ऑनलाइन न्यायाधीश गतिशील प्रोग्रामिंग समाधान

Question

मैं बाइनरी खोज विधि का उपयोग कर Copying Books Problem को हल कर सकता हूं क्योंकि इसे कार्यान्वित करना आसान है। लेकिन मैं सिर्फ गतिशील प्रोग्रामिंग समस्याओं को सुलझाने शुरू कर दिया है और मैं इस समस्या

पुस्तक मुद्रण के आविष्कार से पहले के लिए गतिशील प्रोग्रामिंग समाधान जानना चाहता था, यह एक पुस्तक की एक प्रतिलिपि बनाने के लिए बहुत मुश्किल था। सभी सामग्रियों को द्वारा लिखे गए लेखकों द्वारा हाथ से फिर से लिखा जाना था। लेखक को एक किताब दी गई थी और कई महीनों के बाद उन्होंने अपनी प्रति समाप्त कर दी थी। 15 वीं शताब्दी में सबसे मशहूर लेखक में रहते थे और उनका नाम ज़ेवरियस एंड्रिकस रेमियस ओन्टीस ज़ेंड्रियनस (जेरोक्स) था। वैसे भी, काम बहुत परेशान और उबाऊ था। और इसे गति देने का एकमात्र तरीका अधिक लेखकों को किराए पर लेना था।

एक समय पर, एक थिएटर पहनावा था जो प्रसिद्ध प्राचीन त्रासदी खेलना चाहता था। इन नाटकों की लिपियों को में बांटा गया था, कई पुस्तकों और कलाकारों को निश्चित रूप से उनकी प्रतियों की आवश्यकता थी। इसलिए वे ने इन पुस्तकों की प्रतिलिपि बनाने के लिए कई लेखकों को नियुक्त किया। कल्पना करें कि आपके पास पुस्तकें (क्रमांकित 1, 2, ...., एम) हो सकता है कि पृष्ठों (p_1, p_2, ..., p_m) की एक अलग संख्या हो और आप एक प्रतिलिपि बनाना चाहते हैं उनमें से प्रत्येक । आपका काम इन पुस्तकों को के शास्त्रीय, के < = मीटर के बीच विभाजित करना है। प्रत्येक पुस्तक को केवल एक ही लेखक को सौंपा जा सकता है, और प्रत्येक लेखक को किताबों का निरंतर अनुक्रम प्राप्त करना होगा। इसका मतलब है कि, वहाँ संख्या की एक बढ़ती हुई उत्तराधिकार मौजूद 0 = b_0 < b_1 < b_2, ... < b_ {k-1} < = b_k = मी $ ऐसी है कि आई-वें खुरचने का औजर संख्या के साथ किताबें का एक अनुक्रम हो जाता है द्वि -1 + 1 और द्वि के बीच। की प्रतिलिपि बनाने के लिए आवश्यक समय सभी पुस्तकों को उस लेखक द्वारा निर्धारित किया जाता है जिसे सबसे अधिक कार्य सौंपा गया था। इसलिए, हमारा लक्ष्य एक ही लेखक को सौंपा गया पृष्ठों की अधिकतम संख्या को कम करना है। आपका काम इष्टतम असाइनमेंट ढूंढना है।

बाइनरी खोज के लिए मैं निम्नलिखित कर रहा हूं।

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

यहां पाइथन में लिखा गया एक संभावित गतिशील प्रोग्रामिंग समाधान है। मैं 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 एक सूची जहां ith तत्व ith मुंशी करने के लिए सौंपा पुस्तक अनुक्रमित की एक सूची है के रूप में असाइनमेंट लौटाने अनुक्रमण का उपयोग करें। असाइनमेंट का स्कोर भी वापस कर दिया जाता है (असाइनमेंट में एक लेखक को कॉपी करने के लिए पृष्ठों की अधिकतम संख्या)।

गतिशील प्रोग्रामिंग की कुंजी सबसे पहले सबप्रोबलेम की पहचान करना है। इस मामले में, पुस्तकों का आदेश दिया जाता है और केवल अनुक्रमिक रूप से असाइन किया जा सकता है। इस प्रकार subproblem एस scrib का उपयोग कर अंतिम एन किताबों के लिए एक इष्टतम असाइनमेंट खोजने के लिए है (जहां एन < मीटर और एस < के)। निम्न उपप्रणाली का उपयोग करके छोटे उपप्रवाहों के साथ एक सबप्रोबलेम हल किया जा सकता है: न्यूनतम ("वर्तमान" लेखक को पुस्तक असाइन करना, पुस्तक को अगले लेखक को असाइन करना)।