LinearParition.java

/*
    Problem: Given an array of integers and number of workers,
             find a fair amount of partitions.
             (sum of each partition may or may not be the same)
    This is a k-partition problem, also known as a fair workload problem.
 */
public class LinearPartition {
    static int INF = Integer.MAX_VALUE;

    // complexity: O(n*k), space O(n*k)
    static int findFairAmount(int[] values, int k) {
        int n = values.length;
        int[] p = new int[n+1];
        p[0] = 0;
        // pre-process, calculates
        for (int i=1; i<=n; i++) {
            p[i] = p[i-1] + values[i-1];
        }
        int[][] M = new int[n+1][k+1];
        for (int i=1; i<=n; i++) {
            M[i][1] = p[i];
        }
        for (int i=1; i<=k; i++) {
            M[1][i] = values[0];
        }
        for (int i=2; i<=n; i++) {
            for (int j=2; j<=k; j++) {
                M[i][j] = INF;
                for (int x=1; x<i; x++) {
                    M[i][j] = Math.min(M[i][j], Math.max(M[x][j-1], p[i]-p[x]));
                }
            }
        }
        return M[n][k];
    }

    // prints how partitions are formed
    static List<List<Integer>> findPartition(int[] values, int k, int amount) {
        List<List<Integer>> result = new ArrayList();
        for (int i=0; i<k; i++) {
            result.add(new ArrayList());
        }
        int index = 0;
        int sum = 0;
        for (int i=0; i<values.length; i++) {
            if (sum + values[i] <= amount) {
                sum += values[i];
            } else {
                index++;
                sum = values[i];
            }
            result.get(index).add(values[i]);
        }
        return result;
    }
    public static void main(String[] args) {
        int[] values0 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int amount = findFairAmount(values0, 3);
        System.out.println("amount: " + amount);
        System.out.println(findPartition(values0, 3, amount));
        amount = findFairAmount(values0, 2);
        System.out.println("amount: " + amount);
        System.out.println(findPartition(values0, 2, amount));
        int[] values1= {1, 2, 3, 4, 5, 6, 7, 8, 15, 21};
        amount = findFairAmount(values1, 3);
        System.out.println("amount: " + amount);
        System.out.println(findPartition(values1, 3, amount));
        amount = findFairAmount(values1, 2);
        System.out.println("amount: " + amount);
        System.out.println(findPartition(values1, 2, amount));
        int[] values2 = {1, 1, 1, 1, 1, 1, 1, 1};
        amount = findFairAmount(values2, 3);
        System.out.println("amount: " + amount);
        System.out.println(findPartition(values2, 3, amount));
        amount = findFairAmount(values2, 4);
        System.out.println("amount: " + amount);
        System.out.println(findPartition(values2, 4, amount));
    }
}

/*
References:
https://www.quora.com/A-group-of-N-integer-numbers-need-to-be-divided-fairly-into-K-subgroups-A-fair-division-is-that-the-max-of-the-sums-of-K-subgroups-is-minimal
http://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK2/NODE45.HTM
http://www3.cs.stonybrook.edu/~algorith/video-lectures/2007/lecture18.pdf
*/