Ranzen Variation Algorithmus

Question

Als Hausaufgaben ich das folgende Programm in Java zu machen:

In einem Bücherregal wir einen Stapel von N Bücher haben, die von K Autoren von Hand kopiert werden müssen. Jedes Buch hat Ui Seiten, wo Ai das Buch ist.

Wir müssen jedem Autor kontinuierliche Bücher vom Stapel geben und wir können die Seiten eines Buches nicht teilen.

Erstellen Sie ein Programm, das den Schreibern Bücher zur Verfügung stellt, aber indem Sie die maximale Anzahl von Seiten minimieren, die ein Schreiber kopieren wird.

Als Eingabe gibt der Benutzer eine Reihe von Zahlen, wobei die erste Zahl ist die Anzahl der Bücher N und die zweite Zahl ist die Anzahl der Autoren K und der Rest der Zahlen sind die Anzahl der Seiten jedes Buch hat .

Als Ausgabe gibt das Programm dem Benutzer die maximale Anzahl der Seiten aus, die ein Schreiber kopieren wird.

Beispiel:

Input: 15 6 30 40 10 40 50 20 30 40 10 70 10 50 30 50 10
Output: 90

In diesem Beispiel ist der erste Schreiber kann nehmen book1 = 30 und book2 = 40 aber kann zum Beispiel book1 = 30 nicht mit book3 = 10 aufnehmen. Mit anderen Worten, du nimmst Bücher nur von der Spitze des Stapels, ohne sie zu vermischen.

Hier ist meine Implementierung:

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

Was ich jedes Mal, dass ich verschmelzen die minimalen Paare Bücher, bis die Länge meiner Liste der Anzahl der Autoren gleich ist, aber es funktioniert nicht, Im Beispiel anstelle von 90 gibt es 100 aus.

Ich habe von Dynamic Programming Lösungen und Brutal Lösungen für Rucksack Probleme gehört, aber in meiner Universität haben sie uns noch nicht über Dynamic Programming gelehrt, so entweder der Professor ist verwirrt über das, was wir wissen, oder er möchte, dass wir eine brutale Lösung finden.

Ich war sicher, dass meine Lösung funktionieren würde, aber aus irgendeinem Grund tut es einfach nicht, wenn Sie mich mit Tipps in einer anderen Lösung in diesem oder wo ich mich getäuscht hätte, würde ich mich sehr freuen.

Sie können mich entweder auf DP-Lösungen oder Brutal-Lösungen verweisen, aber für den Fall, dass Sie mich auf DP-Lösungen hinweisen, sollten Sie wissen, dass ich fast keine Ahnung von DP-Implementierung habe.

EDIT: Ich habe blickte bereits auf einige der Tornister artigen Probleme, aber ich habe nicht mit dieser Variante und einer Nicht-DP-Lösung, die ich war in der Lage zu begreifen

Answer 1

Sie auf die binäre Suche tun konnte gefunden Antworten. Wählen Sie ein Maximum für einen Autor aus, sagen Sie M, und scannen Sie dann das Bucharray von links nach rechts und weisen Sie jedem Schreiber die meisten Bücher zu, die Sie können, ohne M zu überschreiten. Wenn noch Bücher vorhanden sind, müssen Sie M erhöhen. Wenn Sie alle Bücher erfolgreich zugewiesen haben, verringern Sie M.

Answer 2

Dies ist bekannt als die Optimierungsversion der partition problem. Es ist NP-schwer. Es gibt eine eher slick article darüber.Soweit ich das beurteilen kann, gibt es eine ganze Reihe von Heuristiken, um diese zu approximieren, aber keine Methode, die explizit dafür ausgelegt ist, "Abkürzungen zu machen", während man zur genauen Antwort kommt.

Ich hatte ähnliche Probleme wie diese zuvor und meine praktische Umsetzung endete als heuristische Methode (die gierige Methode ist trivial auf eine beliebige Anzahl von Partitionen anzuwenden) und dann ein paar Iterationen der Optimierung (versuchen Sie Swapping/Verschieben einige Gewichte zwischen den Sätzen herum) mit einer Überprüfung nach jeder Optimierung zu früh, wenn die Lösung möglicherweise nicht besser sein kann (P-Seiten für w-Writer bedeutet, dass p/w-Seiten pro Schreiber optimal sind, obwohl w nicht teilt p genau p/w + 1 ist optimal). In Ihrem Fall, da Sie nach einer genauen Lösung suchen, werden Sie letztendlich einen Notfallfall des Brute-Forcing benötigen.

Beachten Sie, dass Sie einfach gefragt werden, was die größte Summe einer der Partitionen ist. Dies ist eigentlich NP-schwer selbst - weniger Informationen zu kennen ist nichts mehr als eine Konstante Faktor Abkürzung.

Wenn ich du wäre, würde ich es nur brutal erzwingen. Mit einer kleinen Anzahl von Büchern (weniger als zehn bis zwanzig) und großen Seitenzahlen (100 bis 1000) ist es wahrscheinlich genug, dass es nicht machbar ist, in der Nähe von P/W zu sein, um den Früh-Out-Zustand zu erreichen. Auf der anderen Seite, wenn Sie mit einer beliebigen Anzahl von Büchern umgehen müssen, haben Sie rohe Gewalt für kleine Größen und ungefähre für größere Größen.