Динамическое программирование - определение состояния

Question

Я недавно столкнулся с этой проблемой в учебной программе динамического программирования, и я честно понятия не имею, как определить подходящее состояние.

Вы дали N (1 < = N < = 70) абзацы и M (1 < = M < = N) цифры. Для каждого абзаца i требуется PL_i (1 < = PL_i < = 100) строки и ссылки не более одного рисунка. На каждую цифру ссылаются ровно один раз (т. Е. Никакие два абзаца не могут ссылаться на один и тот же рисунок, а для каждой цифры есть абзац, который ссылается на нее). Каждая цифра требует PF_i (1 < = PF_i < = 100) строк.

Задача состоит в том, чтобы распределить эти рисунки и абзацы на бумаге в том порядке, в котором они указаны, где одна бумага подходит для L строк не более. Ни один абзац или фигура не слишком велика, чтобы соответствовать одной бумаге. Если пункт х помещается на бумаге x_p ссылки фигуру у то у должны быть размещены либо на бумаге x_p - 1 или x_p или x_p + 1.

Мы должны найти минимальное количество строк (и, следовательно, страниц) для распределения, чтобы распределить все цифры и абзацы. Любая помощь будет чрезвычайно оценена. Заранее спасибо!

Answer 1

существует общая проблема, заключающаяся в том, что вы должны переупорядочить параграфы P и рисунки P простого (P, F) порядка или (F, P) упорядочения.

Размещение в документе: (P1, F1), (P2, F2), (P3, F3), где каждый кортеж (P, F) может быть любого порядка (P, F) или (F, P) и существуют некоторые Fs, длина которых 0, что означает, что нет F.

Проблема состоит в том, чтобы найти порядок для каждой пары (P, F).

Одно решение для нахождения наименьшего числа Paiges применяет это правило

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

Хорошо, есть недостаток прототипа этой функции, но для C идет как

calc_spend_lines(pfpairs * pairs) 

Где pfpaires является

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

И вы знаете, что достигли конца, когда P, например, 0.

Все, что вам нужно сделать, это сделать функцию, которая реализует этот специальный знак +, имея в виду разрывы страниц и мертвые строки.

Это дает решение O (N), для минимальнога над количеством страниц, но не количеством строк, так как ваше состояние окончания будет 0.

Если вы хотите, чтобы минимизировать избыточное количество строк, которые вы можете использовать биективности где вы задали окончание состояние на что-то другое вместо 0 и что дает

O (N * Log (L)) раствор

EDIT
Поскольку могут быть другие P между ними тока P и F, один просто нужно проверить вместо ((F, P) , (P, F)) также проверяют пустую страницу (N), поэтому комбо ((P, F) (P, N, F), (F, P), (F, N, P)). Заключение заключается в том, что вы оказываете более сложный алгоритм, но с той же сложностью. Точка в том, что как только вы проверяете один из 4-х заказов, существует только один простой способ сделать оптимальное позиционирование, просто текущее состояние (строки) немного сложнее.

Answer 2

Сначала я бы рекомендовал построить рекурсивный метод.

Выберите наилучшее из вариантов: начните с абзаца или с рисунком.

На каждом шагу выберите лучший из возможных вариантов: добавьте pagebreak, добавьте следующий рисунок, добавьте следующий абзац. Простой конечный автомат поможет устранить запрещенные варианты (например, 2 строки в строке), но это необязательно.

Когда рекурсивное решение будет проверено, вы можете преобразовать его в динамическое программирование сверху вниз или снизу вверх, как описано в большинстве алгоритмических курсов, посвященных DP.

Answer 3

В качестве состояния DP для текущей страницы P вы можете использовать массив (размер L * 2), индексированный по количеству строк, зарезервированный на странице P для цифр, ссылка на страницу P + 1 или (отрицание) количество строк, необходимо на странице P + 1 для фигур, ссылки со страницы П.

Каждый элемент массива состоит из двух значений:

1. х - число пунктов, распределенных на страницах 1 .. П;
2. некоторые данные, необходимые для восстановления распределения точек/фигур после завершения алгоритма DP.

Используйте этот массив для вычисления массива для следующей страницы (P + 1). Для каждого допустимого элемента массива P добавьте новые абзацы (x +1, x +2, ...) на страницу P + 1, обновляя соответствующие элементы массива P + 1. Хотя это возможно, поместите цифры, указанные в этих параграфах, на странице P, затем на странице P + 1, а затем на странице P + 2. Перезаписать элементы массива P + 1, имеющие более низкие значения x, с более высокими значениями.

Временная сложность этого алгоритма O (L * N): строк на странице раза число-пунктов. Поскольку обработка каждой страницы равна O (строки на странице), средние абзацы на страницу.

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; 
}