An optimization problem using dp

algo.java

/*
 * U = { x1, x2, ... , xn }
 * A, B is subset of U. A and B are disjoint, and SUM(A) > SUM(B).
 * Ask for the minimum SUM(A) / SUM(B)
 */

import java.util.Scanner;

public class Foo {
  public static void main(String[] args) {
    System.out.println("Input: n x1 x2 ... xn");
    Scanner input = new Scanner(System.in);
    int n = input.nextInt();
    int[] u = new int[n];
    for (int i = 0; i < n; i++) {
      u[i] = input.nextInt();
    }

    int sum = 0;
    for (int x : u) sum += x;

    boolean[][][] m = new boolean[n][sum + 1][sum + 1];

    // Init
    for (int i = 0; i < n; i++)
      for (int j = 0; j <= sum; j++)
        for (int k = 0; k <= sum; k++)
          m[i][j][k] = false;

    // Base case
    m[0][0][0] = m[0][u[0]][0] = m[0][0][u[0]] = true;

    // DP
    for (int i = 0; i < n - 1; i++) {
      int inc = u[i + 1];
      int bound = sum - inc;
      for (int j = 0; j <= bound; j++) {
        for (int k = 0; k <= bound; k++) {
          if (m[i][j][k]) {
            m[i + 1][j][k] = true;
            m[i + 1][j + inc][k] = true;
            m[i + 1][j][k + inc] = true;
          }
        }
      }
    }

    int numerator = Integer.MAX_VALUE;
    int denominator = 0;
    for (int a = 1; a <= sum; a++) {
      for (int b = 1; b < a; b++) {
        if (m[n - 1][a][b] && (denominator * a < numerator * b)) {
          System.out.println(numerator + " / " + denominator + " => " + a + " / " + b);
          numerator = a;
          denominator = b;
        }
      }
    }

    System.out.println(numerator + " / " + denominator);
  }
}