knapsack variation algorithm

Question

As a homework I have the following program to make in java:

In a bookcase we have a stack of N books which have to be copied by hand by K writers. Each book has Ui pages where Ai is the book.

We need to give each writer continuous books from the stack and we can't split the pages of a book.

Make a program which will give books to the writers but by minimizing the maximum number of pages a writer will copy.

As an input the user will give a string of numbers, where the first number is the number of books N and the second number is the number of writers K and the rest of the numbers are the number of pages each books has.

As an output the program will output to the user the maximum number of pages a writer will copy.

Example:

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

In this example the first writer can take book1 = 30 and book2 = 40 but cannot take for example book1 = 30 with book3 = 10. In other words you take books only from the top of the stack without mixing them up.

Here is my implementation:

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

What I do is each time I merge together the minimal pair of books until the length of my list is equal to the number of writers but it doesn't work, in the example instead of 90 it outputs 100.

I've heard about Dynamic Programming solutions and Brutal solutions to knapsack like problems but in my university they haven't taught us yet about Dynamic Programming, so either the professor is confused about what we know or he wants us to find a brutal solution.

I was sure my solution would work but for some reason it just doesn't, if you could point me with tips in another solution in this or where I have been mistaken I would be very glad.

You can either point me towards DP solutions or Brutal solutions but in case you point me towards DP solutions beware that I have almost no idea about DP implementation.

EDIT: I have already looked at some of the knapsack-like problems but I could not find one with this variation and a non-DP solution that I was able to comprehend

Answer 1

You could do binary search on the answer. Pick a maximum for a writer to do, say M, and then scan the book array from left to right, assigning each writer the most books you can without exceeding M. If there are any books left, then you must increase M. If you've successfully assigned all the books, decrease M.