数组分割问题

题目：有一个无序、元素个数为2n的正整数数组，要求：如何能把这个数组分割为元素个数为n的两个数组，并使两个子数组之和最接近？

看了编程之美的算法，一直在想算法只求出了最接近的那个和值，没有求出分割的具体分法，后来想想，这个具体的分割的索引值，可以在求和值的时候一起保存下来。代码有点乱，凑活看吧。

 

import java.util.*;
class Node{
	int value;
	List index = new ArrayList();
}
public class Main{
	public static void main(String[] args){
		int a[] = {1,5,7,8,9,6,3,11,20,17};
		//题意保证了a.length一定为偶数
		int n = a.length/2;
		int sum = 0;
		//Heap[i]表示存储从a中取i个数所能产生的和之集合的集合
		List[]  Heap = new List[n+1];
		for(int i=0;i<n+1;i++){
			Heap[i] = new ArrayList();
		}
		
		//计算数组总和
		for(int i=0;i<2*n;i++){
			sum += a[i];
		}
		//初始化Heap[0]
		Node node = new Node();
		node.value = 0;
		Heap[0].add(node);
		
		
		for(int k=1;k<=2*n;k++){
			int updateIndex = min(n-1,k-1);
			for(int j=updateIndex;j>=0;j--){
				for(int i=0;i<Heap[j].size();i++){
					Node oldNode = (Node)Heap[j].get(i);
					int num = oldNode.value;
					List list = oldNode.index;
					//只加入小于等于sum/2的那些值
					if(num+a[k-1]<=sum/2){
						Node newNode = new Node();
						newNode.value = num+a[k-1];
						Iterator iterator = list.iterator();
						while(iterator.hasNext()){
							newNode.index.add(iterator.next());
						}
						newNode.index.add(k-1);
						Heap[j+1].add(newNode);
					}
				}
			}
		}
		//实现比较
		Comparator orderValue = new Comparator(){
			public int compare(Object o1, Object o2){
				Node n1 = (Node)o1;
				Node n2 = (Node)o2;
				return  n1.value-n2.value;
			}
		};
		Collections.sort(Heap[n],orderValue);
		Node h_node = (Node)Heap[n].get(Heap[n].size()-1);
		System.out.println(h_node.value);
		List h_list = h_node.index;
		for(int i=0;i<h_list.size();i++){
			System.out.print(h_list.get(i)+" ");
		}
		System.out.println();
	}
	private static int min(int x, int y){
		return x<y?x:y;
	}
}