动态规划背包问题.

gistfile1.txt

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 一个数组中倒找使得两个数组平均化的解
 * 
 * @author ansj
 * 
 */
public class java {
	// 需要计算的数组.ps已经排好序了
	private static int[] arr = new int[] { 11, 13, 23, 23, 32, 99 };
	// 物品状态0,未放入背包.1放入
	private static int[] status = new int[arr.length];
	// 中位数
	private static int mid = 0;
	// 记录背包中的总数
	static int num = 0;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Arrays.sort(arr);
		// 找到平均数
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
		}
		mid = sum / 2;

		// 构造一个集合使之小于等于mid,此时转化为背包问题
		for (int i = 0; i < arr.length; i++) {
			// 将array[i] 放入背包
			findMid(0, i, new ArrayList<Integer>());
		}

		// 一下代码就是为了打印结果可以忽略
		for (Integer index : maxPath) {
			status[index] = 1;
		}

		List<Integer> result1 = new ArrayList<Integer>();
		List<Integer> result2 = new ArrayList<Integer>();

		for (int i = 0; i < status.length; i++) {
			if (status[i] == 0) {
				result1.add(arr[i]);
			} else {
				result2.add(arr[i]);
			}
		}

		System.out.println("mid is " + mid);
		int sum1 = 0;
		for (Integer integer : result1) {
			sum1 += integer;
		}
		int sum2 = 0;
		for (Integer integer : result2) {
			sum2 += integer;
		}
		System.out.println(result1 + " = " + sum1);
		System.out.println(result2 + " = " + sum2);

	}

	private static int maxMid = 0;
	private static List<Integer> maxPath;

	/**
	 * 从i开始寻找一种组合使其最接近midmid 返回true代表这个路径无必要继续下去了
	 * 
	 * @param i
	 */
	private static void findMid(int sum, int i, List<Integer> path) {
		// TODO Auto-generated method stub
		System.out.println(++num);
		sum += arr[i];
		if (sum > mid) {
			return;
		}

		path.add(i);// 记录路径

		if (maxMid==mid || sum == mid) { // 找到最优路
			maxMid = sum;
			maxPath = path;
			return;
		} else if (maxMid < sum) {
			maxMid = sum;
			maxPath = path;
		}

		i++;
		for (int j = i; j < arr.length; j++) {
			findMid(sum, j, new ArrayList<Integer>(path));
		}
	}

}