数组分割问题
题目：有一个无序、元素个数为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;}}