Programación dinámica: determinar el estado

Question

Recientemente me he enfrentado a este problema en un plan de estudios de programación dinámico, y sinceramente no tengo idea acerca de cómo determinar el estado apropiado.

estás dado N (1 < = N < = 70) párrafos y M (1 < = M < = N) cifras. Cada párrafo i requiere PL_i (1 < = PL_i < = 100) líneas y referencias como máximo una figura. Cada figura se referencia exactamente una vez (es decir, no dos párrafos pueden hacer referencia a la misma figura, y para cada figura hay un párrafo que la referencia). Cada figura requiere PF_i (1 < = PF_i < = 100) líneas.

La tarea consiste en distribuir esas figuras y párrafos en el papel en el orden en que aparecen, donde un papel se ajusta a L líneas como máximo. Ningún párrafo o figura es demasiado grande para caber en un solo papel. Si un párrafo x coloca en un papel x_p referencias cifra y entonces y debe ser colocado ya sea en el papel x_p - 1 o x_p o x_p + 1.

tenemos que encontrar el número mínimo de líneas (y páginas) para asignar el fin de distribuir todas las figuras y párrafos. Cualquier ayuda sería extremadamente apreciada. ¡Gracias por adelantado!

Answer 1

hay un problema general que tiene que volver a ordenar paragraps P y las figuras P éter (P, F) ordenar o (F, P) ordenar.

Colocación en el documento es (P1, F1), (P2, F2), (P3, F3) donde cada tupla (P, F) puede ser de cualquier orden (P, F) o (F, P) y hay algunos F que tienen longitud 0 lo que significa que no hay F.

El problema es encontrar el orden para cada par (P, F).

Una solución para la búsqueda de menor número de Paiges es la aplicación de esta regla

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

Ok, hay una falta de prototipo de esta función, pero para C va como

calc_spend_lines(pfpairs * pairs) 

Dónde pfpaires es

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

Y sabe que llegó al final cuando P es 0, por ejemplo.

Todo lo que tienes que hacer es hacer una función que implemente ese signo + especial teniendo en cuenta los saltos de página y las líneas muertas.

Esto da una solución de O (N), por mínima sobre la cantidad de páginas, pero no el número de líneas, ya que su condición final será 0.

Si desea minimizar el exceso número de líneas que se pueden utilizar en la bisección usted conjunto terminando condición a otra cosa en lugar de 0 y que le da

O (log * N (L)) solución

EDITAR
Puesto que no puede ser otra P entre medio P actual y F, uno solo tiene que verificar en lugar de ((F, P) , (P, F)) también verifican la página en blanco (N), por lo que los combos son ((P, F) (P, N, F), (F, P), (F, N, P)). La conclusión es que terminas algoritmo más complicado, pero con la misma complejidad. El punto es que una vez que comprueba uno de los 4 pedidos, solo hay una forma trivial de realizar un posicionamiento óptimo, solo el estado actual (líneas) es un poco complicado.

Answer 2

Al principio me gustaría recomendar para construir método recursivo.

elegir el mejor de variantes: empezar con el párrafo o con la figura.

A cada paso eligen mejor de las posibles variantes: añadir salto de página, agregue la siguiente figura, añadir el siguiente párrafo. La máquina de estado simple ayudaría a eliminar las variantes prohibidas (por ejemplo, 2 saltos de página en la fila), pero no es necesario.

Cuando se comprobará solución recursiva, puede transformar a arriba hacia abajo o de programación dinámica de abajo hacia arriba, como se describe en la mayor parte de los cursos de algoritmos relativos DP.

Answer 3

Como estado DP para la página actual P puede utilizar una matriz (del tamaño L * 2), indexada por el número de líneas, reservadas en la página P para las figuras, referenciadas desde la página P + 1 o (negadas) número de líneas, es necesario en la página P + 1 para las figuras, con la referencia de la página P.

Cada elemento de la matriz se compone de dos valores:

1. x - el número de párrafos, distribuidos en las páginas 1 .. PAG;
2. algunos datos, necesarios para restaurar la distribución de párrafos/figuras una vez finalizado el algoritmo DP.

Utilice esta matriz para calcular la matriz para la página siguiente (P + 1). Para cada elemento válido de la matriz P, añadir nuevos párrafos (x 1, x 2, ...) a la página P + 1, actualizando los elementos correspondientes de la matriz P + 1. Si bien es posible, coloque las figuras, a las que se hace referencia en estos párrafos, en la página P, luego en la página P + 1, luego en la página P + 2. Sobrescribir elementos de la matriz P + 1, que tienen valores más bajos de x, con valores más altos.

complejidad Tiempo de este algoritmo es O (L * N): Los tiempos de líneas por página de número de párrafos. Debido a que el procesamiento de cada página es O (líneas por página * promedio de párrafos por página).

Answer 4

se puede optimizar, pero es la solución de trabajo:

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