是否很久没抽象和逻辑了呢？ DODO它吧(很基础)四

21. 工作分配问题。
    设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法，为每一个人都分配一件不同的工作，
并使总费用达到最小。

    input：第一行有1个正整数n(1<=n<=20)。接下来的n行每行n个数，表示工作费用。
    output: 输出最小的总费用。

    例如：
    input： 3
            10 2 3
             2 3 4
             3 4 5
    output：9

22. 最佳调度问题。
    假设有n个任务由k个可并行工作的机器来完成。完成任务i所需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部
任务的时间最短。

    输入：第一行有两个正整数n和k。
          第二行的n个正整数是完成n个任务需要的时间。
    输出： 完成全部任务的最短时间。

    例如：
    input：7 3
           2 14 4 16 6 5 3
    output：17

23. 无优先级运算问题。
    给定n个正整数和4个运算符+，-，*，/，且运算符无优先级，如 2+3*5=25.对于任意给定的整数m，试设计一个算法，用以上给出的n个数
和4个运算符，产生整数m，且用的运算次数最少。给出的n个数中每个数最多只能用1次，但每种运算符可以任意使用。
    输入：第一行有2个正整数n和m
          第二行是给定的用于运算的n个正整数。
    输出：将计算出的产生整数m的最少无优先级运算次数以及最优无优先级运算表达式输出。

    例如：
    input：5 25
           5 2 3 6 7
    output：2
            2+3*5

24. 算24点问题。
    给定4个正整数， 用算术运算符+，-，*，/将这4个正整数连接起来，使最终的得数恰好为24.

    例如：
    input：1 2 3 7
    output： 2+1=3; 3*7=21; 21+3=24

评论

1 楼 maozj 2010-06-11  

21.工作分配问题。

package abstractandlogic;

/**
 * 21.工作分配问题。 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法，为每一个人都分配一件不同的工作， 并使总费用达到最小。
 * 
 * input：第一行有1个正整数n(1<=n<=20)。接下来的n行每行n个数，表示工作费用。 output: 输出最小的总费用。
 * 
 * @since jdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.08
 * 
 */
public class BestWorkAttemper {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 3;
		int[][] c = { { 0, 0, 0, 0 }, { 0, 10, 2, 3 }, { 0, 2, 3, 4 },
				{ 0, 3, 4, 5 } };
		// 一个测试案例
		BestWorkAttemper bwt = new BestWorkAttemper(n, c);
		bwt.tryi(1);
		int[] bx = bwt.getBestx();
		int bf = bwt.getBestf();

		// 输出
		for (int i = 1; i <= n; i++) {
			System.out.print(bx[i] + " ");
		}
		System.out.println("\n" + bf);
	}

	private int n; // n个工作
	private int[][] c; // 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij
	private int[] x; // n个工作的排列解空间
	private int[] bestx; // 最优解空间
	private int bestf; // 最优解

	/**
	 * 构造方法
	 * 
	 * @param _n
	 * @param _c
	 */
	public BestWorkAttemper(int _n, int[][] _c) {
		n = _n;
		c = _c;
		x = new int[n + 1];
		bestx = new int[n + 1];
		bestf = 36237;

		for (int i = 1; i <= n; i++) {
			x[i] = i;
		}
	}

	/**
	 * 回溯搜索
	 * 
	 * @param i
	 */
	public void tryi(int i) {
		if (i > n) {
			compute();
		} else {
			for (int j = i; j <= n; j++) {
				swap(x, i, j);
				tryi(i + 1);
				swap(x, i, j);
			}
		}
	}

	/**
	 * 交换
	 * 
	 * @param x
	 * @param i
	 * @param j
	 */
	private void swap(int[] x, int i, int j) {
		int temp = x[i];
		x[i] = x[j];
		x[j] = temp;

	}

	/**
	 * 计算最优
	 */
	private void compute() {
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			sum += c[i][x[i]];
		}

		if (sum < bestf) {
			bestf = sum;
			for (int i = 1; i <= n; i++) {
				bestx[i] = x[i];
			}
		}
	}

	/**
	 * 获得最优工作次序
	 * 
	 * @return
	 */
	public int[] getBestx() {
		return bestx;
	}

	/**
	 * 获得最小费用
	 * 
	 * @return
	 */
	public int getBestf() {
		return bestf;
	}

}