学步园

1，问题：有一个含有N个整型数据的数组，将这个数组中的元素分为2堆，使得2堆数据的和之差最小。

最初看到这个题目，第一反应是循序遍历数组，加之，（有点贪心算法的味道），后思不可解。

于是继续探索，将这个问题 转换一下，可知 实际上可以转换为 求解 一个集合的子集问题：

因为 一个数组中所有的N个元素， 用一种方法取走m<=N个元素 ， 那么剩下的N-m个元素自然就属于剩下的一堆。

由   划分成两堆数据  => 取出一些元素 ，并且 附加条件就是 取出的所有元素之和sum1 趋向于 数组所有元素之和 sum 的一半。

2，全排列的递归算法解决：

package net.mldream.algorithm.pr ;

public class Pr01 {

	public static void swap(int[] num, int a, int b) {
		int temp = num[a] ;
		num[a] = num[b] ;
		num[b] = temp ;
	}
	public static void printArray(int[] num,int low, int n) {
		for(int i=low;i<=n;i++) {
			System.out.print(num[i]+" + ") ;
		}
	}

	public static void getAll(int[] num, int low, int high) {
		//printArray(num,low,high) ;
		if(low > high) {
			for(int i = 0; i <= high; i++)             
            System.out.print(num[i]);         
        System.out.println("");  
		} else {
			for(int i=low;i<=high;i++) {
				swap(num,low,i) ;
				
				//System.out.println("num[0]:"+num[0]+" low:" +low+" high:"+high) ;
				getAll(num,low+1,high) ;
				swap(num,low,i) ;
			}
		}
	}

	public static void main(String[] args) {
		int[] num = {1,2,3} ;
		getAll(num,0,2) ;
		//printArray(num, 5) ;
	}
}

但是递归毕竟是一种效率上不占优的算法。

感兴趣的猿们可以 自己尝试一些更优解。或是给出一种方案 解决 一类 问题。这应该会是件 有意思的事情吧？！