dan.java

N皇后问题

package yus.part1;

public class Dan {

	/**
	 * @param args
	 */

	private final static Double MAX = 10000.0;

	public static void main(String[] args) {
		double a[][] = { { 0, 2, -3, 3 }, { 7, 1, 1, -1 }, { -7, -1, -1, 1 },
				{ 4, 1, -2, 2 } };

		boolean flag = true;
		while (a[0][1] > 0 || a[0][2] > 0 || a[0][3] > 0) {

			flag = Simplex(a);
			if (flag == false)
				break;
		}

		if (flag == false)
			System.out.println("unbounded");
		else {
			a[0][0] = -a[0][0];
		}
		System.out.println("The result is: " + a[0][0]);
	}

	private static boolean Simplex(double[][] a) {
		int t = 0;
		Double[] divValue = new Double[a[0].length];
		double min;

		for (int j = 1; j < a[0].length; j++) {
			if (a[0][j] > 0) {
				t = j;
				break;
			}

		}

		for (int i = 1; i < a.length; i++) {
			if (a[i][t] > 0)
				divValue[i] = a[i][0] / a[i][t];
			else
				divValue[i] = MAX;
		}
		min = divValue[1];
		int k = 1;
		for (int i = 2; i < a.length; i++)
			if (divValue[i] < min) {
				min = divValue[i];
				k = i;
			}
		if (min == MAX)
			return false;
		else
			return Pivot(a, k, t);
	}

	private static boolean Pivot(double[][] a, int r, int c) {

		unitary(a, r, c);
		double m = 0;
		for (int i = 0; i < a.length; i++) {
			if (i != r) {
				m = a[i][c];
				for (int j = 0; j < a[0].length; j++) {
					a[i][j] = a[i][j] - a[r][j] * m;
				}
			}
		}
		return true;
	}

	// 基数行的系数归一
	private static void unitary(double[][] a, int r, int c) {
		double m = a[r][c];
		for (int i = 0; i < a[0].length; i++)
			a[r][i] /= m;
	}
}