题目:有一个无序、元素个数为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;
}
}