Dynamic Programming - Partition Problem

DynamicProgrammingPartitionProblemSolver.java

package partition_problem;


public class DynamicProgrammingPartitionProblemSolver implements ThePartitionProblemSolver {

	public int[] solve(int[] books, int k) {
		assert k > 0 && books.length >= k;

		// prefix sums: sum[k] = books[i..k]
		final int[] sum = new int[books.length];
		
		sum[0] = books[0];
		for (int i = 1; i < books.length; i++) sum[i] = sum[i-1] + books[i];  

		// M[n<=length][m<=k], D[n<=length][m<=k]
		final int[][] M = new int[books.length+1][k+1];
		final int[][] D = new int[books.length+1][k+1];
		
		for (int n = 1; n <= books.length; n++) M[n][1] = sum[n-1];
		for (int m = 1; m <= k; m++) M[1][m] = books[0];

		for (int n = 2; n <= books.length; n++) {
			for (int m = 2; m <= k; m++) {
				M[n][m] = Integer.MAX_VALUE;
				for (int x = 1; x < n; x++) {
					final int largest = Math.max(M[x][m-1], sum[n-1]-sum[x-1]);
					
					if (largest < M[n][m]) {
						M[n][m] = largest;
						D[n][m] = x;
					}
				}
			}
		}
		
		int[] dividers = new int[k-1];
		for (int m = k, n = books.length; m > 1; m--)
			n = dividers[m - 2] = D[n][m];
		return dividers;
	}

	
}

RecursivePartitionProblemSolver.java

/*
 * The Algorithm Design Manual - Dynamic Programming - The Partition Problem
 */
package partition_problem;


public class RecursivePartitionProblemSolver implements ThePartitionProblemSolver {

	private static int sum(int[] x, int begin, int end) {
		int sum = 0;
		for (int i = begin; i < end; i++) sum += x[i];
		return sum;
	}

	private int minimumPossibleLength(int[] books, int n, int k) {
		if (k == 1) return sum(books, 0, n);
		if (n == 1) return books[0];
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			int a = minimumPossibleLength(books, i+1, k - 1);
			int b = sum(books, i+1, n);
			min = Math.min(min, Math.max(a, b));
		}
		return min;
	}
	
	public int[] solve(int[] books, int k) {
		assert k > 0;
		assert books.length >= k;

		int min = minimumPossibleLength(books, books.length, k);
		int[] dividers = new int[k-1];
		int sum = 0, d = 0;
		//System.out.printf("%s, %d => %d\n", Arrays.toString(books), k, min);
		for (int i = 0; i < books.length; i++) {
			if (sum + books[i] > min) {
				dividers[d++] = i;
				sum = books[i];
			} else {
				sum += books[i];
			}
		}
		assert d == dividers.length;
		return dividers;
	}

}

ThePartitionProblemSolver.java

package partition_problem;

public interface ThePartitionProblemSolver {

	public int[] solve(int[] books, int k);

}

ThePartitionProblemTest.java

package partition_problem;

import static org.junit.Assert.assertArrayEquals;

import java.util.Arrays;

import org.junit.Before;
import org.junit.Test;

public class ThePartitionProblemTest {

	private ThePartitionProblemSolver solution;

	@Before
	public void setUp() {
		solution = new DynamicProgrammingPartitionProblemSolver();
	}

	@Test(timeout=2000)
	public void onlyOneWorker() {
		int[] books = { 100, 100, 100, 100, 100, 100, 100, 100, 100, };
		assertArrayEquals(new int[]{}, solution.solve(books, 1));
	}

	@Test(timeout=2000)
	public void twoWorker() {
		int[] books = { 400, 800, };
		assertArrayEquals(new int[]{1}, solution.solve(books, 2));
	}

	@Test(timeout=2000)
	public void sameLength() {
		int[] books = { 100, 100, 100, 100, 100, 100, 100, 100, 100, };
		assertArrayEquals(new int[]{3, 6}, solution.solve(books, 3));
	}

	@Test(timeout=2000)
	public void sameAmounts() {
		int[] books = { 100, 100, 100, 100, 200, 200, 400, };
		assertArrayEquals(new int[]{4, 6}, solution.solve(books, 3));
	}

	@Test(timeout=2000)
	public void testCase1() {
		int[] books = { 100, 200, 300, 400, 500, 600, 700, 800, 900};
		assertArrayEquals(new int[]{5, 7}, solution.solve(books, 3));
	}
	
	@Test(timeout=2000)
	public void manyBooks() {
		final int n = 1000;
		int[] books = new int[n]; 
		Arrays.fill(books, 100);
		assertArrayEquals(new int[]{n/4, n/2, n/4*3}, solution.solve(books, 4));
	}
}