गतिशील प्रोग्रामिंग - राज्य का निर्धारण

Question

मुझे हाल ही में एक गतिशील प्रोग्रामिंग पाठ्यक्रम में इस समस्या का सामना करना पड़ा है, और मुझे ईमानदारी से उचित स्थिति निर्धारित करने के बारे में कोई जानकारी नहीं है।

आप एन (1 < = एन < = 70) पैराग्राफ और एम (1 < = एम < = एन) के आंकड़े दिया जाता है। प्रत्येक अनुच्छेद iPL_i (1 < = PL_i < = 100) अधिकांश एक पंक्ति में रेखाएं और संदर्भों की आवश्यकता है। प्रत्येक आकृति को एक बार संदर्भित किया जाता है (यानी, कोई भी पैराग्राफ एक ही आंकड़े का संदर्भ नहीं दे सकता है, और प्रत्येक आकृति के लिए एक पैराग्राफ है जो इसका संदर्भ देता है।) प्रत्येक आकृति को पीएफ_आई (1 < = पीएफ_आई < = 100) लाइनों की आवश्यकता होती है।

कार्य उन आंकड़ों और अनुच्छेदों को कागज पर वितरित करने के क्रम में वितरित करना है, जहां एक पेपर एल लाइनों के लिए फिट बैठता है। एक पेपर पर फिट करने के लिए कोई पैराग्राफ या आकृति बहुत बड़ी नहीं है। एक पैराग्राफ एक्स कागज पर x_p संदर्भ एक आंकड़ा दे रखा है y तो y या तो कागज पर रखा जाना चाहिए x_p - 1 या x_p या x_p + 1।

हमें सभी आंकड़ों और अनुच्छेदों को वितरित करने के लिए आवंटित करने के लिए न्यूनतम पंक्तियों (और इस प्रकार पृष्ठ) को ढूंढना होगा। किसी भी मदद की सराहना की जाएगी। अग्रिम में धन्यवाद!

Answer 1

सामान्य समस्या है कि आपको पैराग्राप्स पी और आंकड़े पी ईथर (पी, एफ) ऑर्डर या (एफ, पी) ऑर्डरिंग को रेडियोडर करना होगा।

दस्तावेज़ में रखना (पी 1, एफ 1), (पी 2, एफ 2), (पी 3, एफ 3) जहां प्रत्येक ट्यूपल (पी, एफ) किसी ऑर्डर (पी, एफ) या (एफ, पी) का हो सकता है और कुछ एफएस हैं जिनकी लंबाई 0 है, इसका मतलब है कि कोई एफ

समस्या प्रत्येक (पी, एफ) जोड़ी के लिए ऑर्डर करने के लिए है। Paiges की कम से कम संख्या को खोजने के लिए

एक समाधान यह नियम लागू कर रहा है

lines_total = MIN(lines(P,F),lines(F,P)) + remaining() //this is custom addition 

ठीक है, वहाँ इस समारोह के प्रोटोटाइप का अभाव है, लेकिन सी के लिए की तरह

calc_spend_lines(pfpairs * pairs) 

कहाँ pfpaires

है चला जाता है

typedef struct 
{ 
    int P; 
    int F; 
} pfpaires; 

और आप जानते हैं कि उदाहरण के लिए पी 0 है जब आप अंत तक पहुंच गए हैं।

आपको बस इतना करना है, कार्य करना है, जो उस विशेष + चिह्न को ध्यान में रखता है जो पेज ब्रेक और मृत रेखाओं में है।

यह पृष्ठों की संख्या नहीं बल्कि लाइनों की संख्या से अधिक हे (एन) समाधान देता है, कम से कम के लिए, के बाद से अपने अंत हालत 0.

हो जाएगा आप लाइनों आप द्विभाजन जहां उपयोग कर सकते हैं की संख्या से अधिक कम करने के लिए चाहते हैं आप और 0 के बजाय कुछ करने के लिए शर्त को समाप्त हुए सेट और चूंकि वर्तमान पी और एफ inbetween अन्य पी हो सकता है कि आप

हे (एन * लॉग (एल)) समाधान

संपादित
देता है, एक बस इसके बजाय जांचना है ((एफ, पी) , (पी, एफ)) रिक्त पृष्ठ (एन) के लिए भी जांच करें ताकि combos ((पी, एफ) (पी, एन, एफ), (एफ, पी), (एफ, एन, पी) हैं। निष्कर्ष यह है कि आप अधिक जटिल एल्गोरिदम समाप्त करते हैं, लेकिन समान जटिलता। प्वाइंट यह है कि एक बार जब आप 4 ऑर्डरिंग में से किसी एक को चेक करते हैं, तो इष्टतम स्थिति बनाने के लिए केवल एक छोटा रास्ता है, केवल वर्तमान स्थिति (रेखाएं) थोड़ा जटिल है।

Answer 2

पहले मैं रिकर्सिव विधि बनाने की सिफारिश करता हूं।

वेरिएंट से सर्वश्रेष्ठ चुनें: अनुच्छेद या आकृति के साथ शुरू करें।

प्रत्येक चरण में संभावित रूपों से सर्वश्रेष्ठ चुनें: पेजब्रेक जोड़ें, अगला चित्र जोड़ें, अगला अनुच्छेद जोड़ें। सरल राज्य मशीन निषिद्ध रूपों को खत्म करने में मदद करेगी (उदाहरण के लिए, पंक्ति में 2 पेजब्रैक), लेकिन यह आवश्यक नहीं है।

जब रिकर्सिव समाधान की जांच की जाएगी, तो आप इसे डीपी से संबंधित अधिकांश एल्गोरिदमिक पाठ्यक्रमों में वर्णित अनुसार ऊपर-नीचे या नीचे-गतिशील प्रोग्रामिंग में बदल सकते हैं।

Answer 3

वर्तमान पृष्ठ पी आप (आकार एल * 2 की) एक सरणी, लाइनों की संख्या द्वारा अनुक्रमित उपयोग कर सकते हैं, आंकड़े के लिए पेज पी पर आरक्षित के लिए एक डीपी राज्य, पेज पी + 1 या से संदर्भित के रूप में (नकार दिया गया) लाइनों की संख्या, पेज पी + 1 आंकड़े के लिए पर की जरूरत है, पेज पी

प्रत्येक सरणी तत्व से संदर्भित दो मूल्यों के होते हैं:

1. एक्स - पैराग्राफ की संख्या, पृष्ठों 1 पर वितरित .. पी;
2. डीपी एल्गोरिदम समाप्त होने के बाद पैराग्राफ/आंकड़े वितरण को पुनर्स्थापित करने के लिए आवश्यक कुछ डेटा।

अगले पृष्ठ (पी + 1) के लिए सरणी गणना करने के लिए इस सरणी का उपयोग करें। सरणी पी के प्रत्येक मान्य तत्व के लिए, नए पैराग्राफ जोड़ें (x +1, x +2, ...) पृष्ठ पी + 1, सरणी पी + 1 के संवाददाता तत्वों को अद्यतन करने के लिए। हालांकि यह संभव है, पेज पैरा पर, इन पैराग्राफों द्वारा संदर्भित आंकड़े रखें, फिर पृष्ठ पी + 1 पर, पृष्ठ पी + 2 पर। उच्च मूल्यों के साथ, x के निम्न मान वाले सरणी P + 1 के तत्वों को ओवरराइट करें। इस एल्गोरिथ्म के

समय जटिलता ओ (एल * एन) है: लाइनों-प्रति-पेज बार संख्या के- पैराग्राफ। चूंकि प्रत्येक पृष्ठ को प्रोसेस करना ओ (लाइन-प्रति-पृष्ठ * औसत-पैराग्राफ-प्रति-पृष्ठ) है।

Answer 4

अनुकूलित कर सकते हो, लेकिन यह समाधान काम कर रहा है:

 
public class ParagraphsAndFigures {
 

 public static ArrayList<PageContent> generatePages(List<Paragraph> paragraphs, int L) { 
      ArrayList<PageContent> pages = new ArrayList<PageContent>(); 
      for (int i = 0; i < paragraphs.size() * 2; i++) { 
       pages.add(new PageContent()); 
      } 
      int page = 0; 

      for (Paragraph paragraph : paragraphs) { 
       do { 
        int cur = pages.get(page).linesReserved; 
        int next = pages.get(page + 1).linesReserved; 

        if (cur + paragraph.size < L) { 
         cur += paragraph.size; 

         if (paragraph.figure != null) { 

          if (pages.get(page + 1).hasPicture()) { 
           if (next + paragraph.figure.size < L) { 
            pages.get(page).texts.add(paragraph); 
            pages.get(page + 1).texts.add(paragraph.figure); 
            pages.get(page).linesReserved += paragraph.size; 
            pages.get(page + 1).linesReserved += paragraph.figure.size; 
            break; // next paragraph 
           } else { 
            page++; 
            continue; 
           } 
          } 

          if (pages.get(page).hasPicture()) { 
           if (cur + paragraph.figure.size < L) { 
            pages.get(page).texts.add(paragraph); 
            pages.get(page).texts.add(paragraph.figure); 
            pages.get(page).linesReserved += paragraph.size; 
            pages.get(page).linesReserved += paragraph.figure.size; 
            break; // next paragraph 
           } else { 
            if (next + paragraph.figure.size < L) { 
             pages.get(page).texts.add(paragraph); 
             pages.get(page + 1).texts.add(paragraph.figure); 
             pages.get(page).linesReserved += paragraph.size; 
             pages.get(page + 1).linesReserved += paragraph.figure.size; 
             break; // next paragraph 
            } 
            page++; 
            continue; 
           } 
          } 

          if (page != 0 && pages.get(page - 1).hasPicture()) { 
           int prev = pages.get(page - 1).linesReserved; 
           if (prev + paragraph.figure.size < L) { 
            pages.get(page).texts.add(paragraph); 
            pages.get(page - 1).texts.add(paragraph.figure); 
            pages.get(page).linesReserved += paragraph.size; 
            pages.get(page - 1).linesReserved += paragraph.figure.size; 
            break; // next paragraph 
           } else { 
            if (cur + paragraph.figure.size < L) { 
             pages.get(page).texts.add(paragraph); 
             pages.get(page).texts.add(paragraph.figure); 
             pages.get(page).linesReserved += paragraph.size; 
             pages.get(page).linesReserved += paragraph.figure.size; 
             break; // next paragraph 
            } 
            if (next + paragraph.figure.size < L) { 
             pages.get(page).texts.add(paragraph); 
             pages.get(page + 1).texts.add(paragraph.figure); 
             pages.get(page).linesReserved += paragraph.size; 
             pages.get(page + 1).linesReserved += paragraph.figure.size; 
             break; // next paragraph 
            } 
            page++; 
           } 
          } 

          if (page != 0) { 
           int prev = pages.get(page - 1).linesReserved; 
           if (prev + paragraph.figure.size < L) { 
            pages.get(page).texts.add(paragraph); 
            pages.get(page - 1).texts.add(paragraph.figure); 
            pages.get(page).linesReserved += paragraph.size; 
            pages.get(page - 1).linesReserved += paragraph.figure.size; 
            break; // next paragraph 
           } 
          } 

          if (cur + paragraph.figure.size < L) { 
           pages.get(page).texts.add(paragraph); 
           pages.get(page).texts.add(paragraph.figure); 
           pages.get(page).linesReserved += paragraph.size; 
           pages.get(page).linesReserved += paragraph.figure.size; 
           break; // next paragraph 
          } 

          if (next + paragraph.figure.size < L) { 
           pages.get(page).texts.add(paragraph); 
           pages.get(page + 1).texts.add(paragraph.figure); 
           pages.get(page).linesReserved += paragraph.size; 
           pages.get(page + 1).linesReserved += paragraph.figure.size; 
           break; // next paragraph 
          } 
          page++; 
         } 
        } 
        page++; 
       } while (true); 
      } 
      return pages; 
     } 
    } 
 

 And tests: 
 
public class ParagraphsAndFiguresTest { 
      @Test 
      public void pageGeneration1() throws Exception { 
       // given 
       ArrayList paragraphs = new ArrayList(); 
       paragraphs.add(new Paragraph(20,21)); 
       paragraphs.add(new Paragraph(22,23)); 
       paragraphs.add(new Paragraph(24,25));
 

 // when ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50); // then assertThat(transformToList(pageContents), is(asList("20", "21", "p0" ,"22" ,"23", "p1" ,"24" ,"25", "p2"))); } @Test public void pageGeneration2() throws Exception { // given ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>(); paragraphs.add(new Paragraph(10,11)); paragraphs.add(new Paragraph(28,21)); paragraphs.add(new Paragraph(22,23)); // when ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50); // then assertThat(transformToList(pageContents), is(asList("10", "11" ,"28", "p0" ,"21", "22" , "p1" ,"23", "p2"))); } @Test public void pageGeneration3() throws Exception { // given ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>(); paragraphs.add(new Paragraph(10,11)); paragraphs.add(new Paragraph(12,30)); paragraphs.add(new Paragraph(13,19)); // when ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50); // then assertThat(transformToList(pageContents), is(asList("10", "11" ,"12", "13", "p0" ,"30", "19" , "p1"))); } @Test public void pageGeneration4() throws Exception { // given ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>(); paragraphs.add(new Paragraph(10,11)); paragraphs.add(new Paragraph(30,12)); paragraphs.add(new Paragraph(13,16)); // when ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50); // then assertThat(transformToList(pageContents), is(asList("10", "11" ,"12", "16", "p0" ,"30", "13" ,"p1"))); } @Test public void pageGeneration5() throws Exception { // given ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>(); paragraphs.add(new Paragraph(31,32)); paragraphs.add(new Paragraph(17,21)); paragraphs.add(new Paragraph(30,35)); // when ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50); // then assertThat(transformToList(pageContents), is(asList("31", "p0", "32", "17", "p1", "21", "p2", "30", "p3", "35", "p4"))); } private List<String> transformToList(ArrayList<PageContent> pageContents) { List<String> result = new ArrayList<String>(); for (int i = 0; i < pageContents.size(); i++) { PageContent pageContent = pageContents.get(i); if (!pageContent.texts.isEmpty()) { for (Text text : pageContent.texts) { result.add(String.valueOf(text.size)); } result.add("p"+i); } } return result; } } 
 

 And structures: public class PageContent { int linesReserved; Collection texts = new ArrayList();
 

    public boolean hasPicture() { 
     for (Text text : texts) { 
      if (text instanceof Figure) { 
       return true; 
      } 
     } 
     return false; 
    } 
} 

public class Text { 
    protected int size; 
} 
public class Figure extends Text{ 
} 
public class Paragraph extends Text { 

    public Paragraph(int size, int fSIze) { 
     this.size = size; 
     this.figure = new Figure(); 
     this.figure.size = fSIze; 
    } 

    Figure figure; 
}