Take the 2-minute tour ×

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.


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) {

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

    while (booksList.size() > writers) {


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.add(indexA, a + b);

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

share|improve this question
I can see quite a few solutions here <stackoverflow.com/…;. –  g13n Apr 30 '12 at 16:02
@g13n I looked some of the knapsack-like problems in this site but I could not find this particular variation, especially without DP solution –  Jason Kur Apr 30 '12 at 16:03
Did you check out related questions to yours, I can see a bunch of bruteforce solutions ;-) –  g13n Apr 30 '12 at 16:04
is the input complete? –  Paul Vargas Apr 30 '12 at 16:06
I know this is going to sound stupid but most problems had elements with a weight and a value and I could not relate these kind of problems with the books and the pages (maybe it's because of my poor English) that is why I could not understand how to implement these solutions to my own problem –  Jason Kur Apr 30 '12 at 16:09
show 6 more comments

2 Answers

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.

share|improve this answer
I have seen this as a valid answer before, it's just that my programming skills aren't really good to do something delicate as that –  Sillicon Touch Apr 30 '12 at 16:51
Could you possibly give me some more details on how to implement this? –  Jason Kur May 2 '12 at 12:47
Pick an M. Doesn't really matter how, start with 1. Starting from the top of the stack of books, start assigning books to the first writer. Keep assigning books to first writer, one at a time, until the next book would assign the first writer more than M pages. The first writer is complete, start again with the second writer. And so on. If you assign all the books successfully, M++ and try again. If you have books left over, M-- and try again. –  Keith Randall May 2 '12 at 16:22
add comment

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.

share|improve this answer
I have actually tried the pages per writer solution and yes if it does not divide exactly then it leads to nowhere –  Jason Kur Apr 30 '12 at 16:42
add comment

Your Answer


