mochila algoritmo de variación

Question

Como la tarea que tengo el siguiente programa para hacer en Java:

En una estantería tenemos una pila de libros de N que tienen que ser copiados a mano por escritores K. Cada libro tiene páginas Ui donde Ai es el libro.

Necesitamos dar a cada escritor libros continuos de la pila y no podemos dividir las páginas de un libro.

Realice un programa que le dará libros a los escritores pero minimizando el número máximo de páginas que copiará un escritor.

Como entrada el usuario dará una cadena de números, donde el primer número es el número de libros N y el segundo número es el número de escritores K y el resto de los números es el número de páginas que cada libro tiene .

Como salida, el programa generará para el usuario el número máximo de páginas que copiará un escritor.

Ejemplo:

de entrada: 15 6 30 40 10 40 50 20 30 40 10 70 10 50 30 50 10
de salida: 90

En este ejemplo el primer escritor puede tomar Libro1 = 30 y book2 = 40 pero no puede tomar, por ejemplo, book1 = 30 con book3 = 10. En otras palabras, toma los libros solo desde la parte superior de la pila sin mezclarlos.

Aquí es mi aplicación:

import java.util.*; 

public class Library { 

public static void main(String[] args) { 
    Scanner input = new Scanner(System.in); 

    // to work with 1.6 erase the second "Integer" 
    //in 1.7 this works properly 
    List<Integer> booksList = new LinkedList<Integer>(); 
    System.out.printf("Give: "); 

    String answer = input.nextLine(); 
    String[] arr = answer.split(" "); 

    for (String num : arr) { 
     booksList.add(Integer.parseInt(num)); 
    } 

    int books = booksList.remove(0); 
    int writers = booksList.remove(0); 

    while (booksList.size() > writers) { 
     mergeMinimalPair(booksList); 
    } 

    System.out.println(getMax(booksList)); 
} 

public static void mergeMinimalPair(List<Integer> books) { 
    int index = 0; 
    int minValue = books.get(0) + books.get(1); 
    for (int i = 1; i < books.size() - 1; i++) { 
     if ((books.get(i) + books.get(i + 1)) < minValue) { 
      index = i; 
      minValue = books.get(i) + books.get(i + 1); 
     } 
    } 
    combine(books, index, index + 1); 
} 

public static void combine(List<Integer> books, int indexA, int indexB) { 
    Integer a = books.get(indexA); 
    Integer b = books.get(indexB); 
    books.remove(indexB); 
    books.add(indexA, a + b); 
    books.remove(indexB); 
} 

public static int getMax(List<Integer> books) { 
    int max = books.get(0); 
    for (int i = 1; i < books.size(); i++) { 
     if (books.get(i) > max) { 
      max = books.get(i); 
     } 
    } 
    return max; 
} 
} 

Lo que hago es cada vez que se funden el par mínimo de libros hasta que la longitud de mi lista es igual al número de escritores, pero que no funciona, en el ejemplo en lugar de 90 muestra 100.

He oído hablar de soluciones de programación dinámica y soluciones brutales a los problemas de mochilas pero en mi universidad todavía no nos han enseñado acerca de la programación dinámica, por lo que el profesor está confundido sobre lo que sabemos o quiere que encontremos una solución brutal.

Estaba seguro de que mi solución funcionaría, pero por alguna razón no funciona, si me puede dar consejos sobre otra solución en esta o en la que me he equivocado, estaría muy contento.

Puede dirigirme hacia las soluciones DP o Brutal, pero en caso de que me señale las soluciones DP, tenga en cuenta que casi no tengo idea acerca de la implementación de DP.

EDIT: Ya he mirado algunos de los problemas de la mochila-como, pero no pude encontrar uno con esta variación y una solución no-DP que yo era capaz de comprender

Answer 1

Se podría hacer una búsqueda binaria en el responder. Elija un máximo para que lo haga un escritor, digamos M, y luego escanee el conjunto de libros de izquierda a derecha, asignando a cada escritor la mayor cantidad posible de libros sin exceder M. Si quedan libros, debe aumentar M. Si ha asignado correctamente todos los libros, disminuya M.

Answer 2

Esto se conoce como la versión de optimización de partition problem. Es NP-Hard. Hay un más bien slick article al respecto, también.Por lo que puedo decir, hay una buena cantidad de heurísticas para aproximarlo, pero ningún método explícitamente diseñado para "tomar atajos" mientras se llega a la respuesta exacta.

He tenido problemas similares a esto antes y mi implementación práctica terminó siendo un método heurístico (el método codicioso es trivial para aplicar a un número arbitrario de particiones) y luego algunas iteraciones de optimización (intente cambiar/mover algunos pesos entre los conjuntos alrededor) con un control después de cada optimización para anticipar si la solución no puede ser mejor (páginas p para escritores w significa páginas p/w por escritor es óptimo, aunque si w no se divide p exactamente p/w + 1 es óptimo). En su caso, ya que está buscando una solución exacta, en última instancia necesitará una copia de seguridad de la fuerza bruta.

Tenga en cuenta que simplemente se le pregunta cuál es la suma más grande de una de las particiones. En realidad, esto es NP-hard, saber que menos información no es más que un atajo de factor constante.

Si fuera usted, simplemente lo forzaría brutalmente. Con un número pequeño de libros (menos de diez a veinte) y un gran número de páginas (100 a 1000) es probable que acercarse a p/w no sea factible para alcanzar la condición de salida anticipada. Por otro lado, si necesita manejar cualquier número de libros, tenga la fuerza bruta para tamaños pequeños y aproximados para tamaños más grandes.