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

This is known as the optimization version of the partition problem. It is NP-Hard. There's a rather slick article about it, too. As far as I can tell, there's a good many heuristics for approximating it, but no method explicitly designed for "taking short cuts" while getting to the exact answer.

I've had problems similar to this before and my practical implementation ended up being a heuristic method (the greedy method is trivial to apply to an arbitrary number of partitions) and then a few iterations of optimization (try swapping/moving some weights between the sets around) with a check after each optimization to early-out if the solution can't possibly be any better (p pages for w writers means p/w pages per writer is optimal, although if w doesn't divide p exactly p/w+1 is optimal). In your case since you're looking for an exact solution, you will need a back up case of brute forcing ultimately.

Note that you're simply asked for what the largest sum of one of the partitions is. This is actually NP-hard itself -- knowing less information isn't anything more than a constant factor shortcut.

If I were you, I'd just brute force it. With a small-ish number of books (less than ten to twenty) and large page counts (100 to 1000) it's likely enough that getting close to p/w isn't feasible to hit the early-out condition. On the other hand, if you need to handle any number of books have it brute force for small sizes and approximate for larger sizes.

Answer 2

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.