zaino algoritmo di variazione

Question

Come compiti a casa ho il seguente programma per fare in Java:

In una libreria abbiamo una pila di libri N che devono essere copiati a mano da scrittori K. Ogni libro ha pagine Ui in cui è il libro Ai.

Abbiamo bisogno di dare a ogni scrittore libri continui dallo stack e non possiamo dividere le pagine di un libro.

Creare un programma che fornirà libri agli autori ma riducendo al minimo il numero massimo di pagine copiate da uno scrittore.

Come input l'utente darà una stringa di numeri, dove il primo numero è il numero di libri N e il secondo numero è il numero di scrittori K e il resto dei numeri è il numero di pagine di ciascun libro .

Come output, il programma restituirà all'utente il numero massimo di pagine che uno scrittore copierà.

Esempio:

ingresso: 15 6 30 40 10 40 50 20 30 40 10 70 10 50 30 50 10
uscita: 90

In questo esempio, il primo scrittore può prendere book1 = 30 e book2 = 40 ma non può prendere ad esempio book1 = 30 con book3 = 10. In altre parole, si prendono i libri solo dalla cima dello stack senza mescolarli.

Qui è la mia realizzazione:

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

Quello che faccio è ogni volta che fondono insieme la coppia minima di libri finché la lunghezza della mia lista è uguale al numero di scrittori, ma non funziona, nell'esempio invece di 90 emette 100.

Ho sentito parlare di soluzioni di programmazione dinamica e soluzioni brutali a problemi di tipo zaino, ma nella mia università non ci hanno ancora insegnato la programmazione dinamica, quindi il professore è confuso su ciò che sappiamo o vuole che troviamo una soluzione brutale.

Ero sicuro che la mia soluzione avrebbe funzionato, ma per qualche ragione semplicemente non lo è, se potessi indicarmi dei suggerimenti in un'altra soluzione in questo o in cui sono stato scambiato sarei molto contento.

È possibile indicarmi soluzioni DP o soluzioni Brutal ma, nel caso in cui mi si punti verso soluzioni DP, fare attenzione a non avere quasi nessuna idea dell'implementazione DP.

EDIT: Ho già guardato alcuni dei problemi zaino-come, ma non sono riuscito a trovare uno con questa variazione e una soluzione non-DP che ero in grado di comprendere

Answer 1

Si potrebbe fare ricerca binaria sul risposta. Scegli un massimo da fare per uno scrittore, ad esempio M, quindi esegui la scansione dell'array di libri da sinistra a destra, assegnando a ciascuno scrittore il maggior numero di libri possibile senza superare lo M. Se sono rimasti dei libri, è necessario aumentare M. Se hai assegnato correttamente tutti i libri, diminuisci M.

Answer 2

Questo è noto come la versione di ottimizzazione dello partition problem. È NP-Hard. C'è anche un po 'di slick article.Per quello che posso dire, ci sono un buon numero di euristiche per approssimarlo, ma nessun metodo esplicitamente progettato per "prendere scorciatoie" mentre si arriva alla risposta esatta.

Ho avuto problemi simili a questo prima e la mia implementazione pratica si è rivelata un metodo euristico (il metodo goloso è banale da applicare a un numero arbitrario di partizioni) e quindi alcune iterazioni di ottimizzazione (prova a scambiare/spostare alcuni pesi tra i set intorno) con un controllo dopo ogni ottimizzazione per uscire in anticipo se la soluzione non può essere migliore (pagine p per w scrittori significa pagine p/w per scrittore è ottimale, anche se w non divide p esattamente p/w + 1 è ottimale). Nel tuo caso, dal momento che stai cercando una soluzione esatta, alla fine avrai bisogno di un caso di riserva di forza bruta.

Nota che ti viene semplicemente chiesto qual è la somma più grande di una delle partizioni. Questo è in realtà NP-hard in sé - conoscere meno informazioni non è altro che una scorciatoia di fattori costante.

Se fossi in te, lo forzai brutalmente. Con un numero ridotto di libri (meno di dieci a venti) e un numero elevato di pagine (da 100 a 1000) è probabile che avvicinarsi al p/w non sia possibile per raggiungere la condizione di early-out. D'altra parte, se hai bisogno di gestire un numero qualsiasi di libri, hai forza bruta per le taglie piccole e approssimativo per le taglie più grandi.