任意2n个整数，从其中选出n个整数，使得选出的n个整数和同剩

模仿动态规划解0-1背包问题的策略，令S(k, i)表示前k个元素中任意i个元素的和的集合。

显然：

S(k, 1) = {A[i] | 1<= i <= k}

S(k, k) = {A[1]+A[2]+…+A[k]}

S(k, i) = S(k-1, i) U {A[k] + x | x属于S(k-1, i-1) }

按照这个递推公式来计算，最后找出集合S(2N, N)中与SUM最接近的那个和，这便是答案。

题目是这样的：

有一个没有排序，元素个数为2N的正整数数组。要求把它分割为元素个数为N的两个数组，并使两个子数组的和最接近。

思路书上都有。

这个if判断，if (j >= A[k] && flag[i - 1][j - A[k]])，j >= A[k]条件是为了让flag数组的第二维不越界。

参考了这个地址：

http://www.cppblog.com/baby-fly/archive/2009/09/24/92392.html

怎么都是用二维数组解决的，用一维数组就可以了啊。
```

public class test6 { public static void main(String[] args) { 
        int[] arr={ 12,45,1,4,77,33,25,41 }; 
        int sum=0; 
        for(int i=0;ilength;i++){
            sum+=arr[i];
        } 
        boolean[] marks=new boolean[sum/2+1];
        marks[0]=true; 
        for(int i=0;ilength;i++){ 
            for(int j=sum/2;j>=arr[i];j--){ 
                if(marks[j-arr[i]])
                    marks[j]=true;
            }
        } 
        for(int j=sum/2;j>=0;j--){ if(marks[j]){
                System.out.println(String.format("sum:%s",sum));
                System.out.println(String.format("part1:%s",j));
                System.out.println(String.format("part2:%s",sum-j));
                System.out.println(String.format("sub:%s",Math.abs(2*j-sum))); break;
            }
        }
    }
}

```

import java.util.Scanner;

public class BeautyPro218 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int len = scanner.nextInt();
			int[] a = new int[len];
			for(int i=0;i<len;i++){
				a[i] =scanner.nextInt();
			}
			splitArr(len, a);
		}
	}
	/*假设数组A[1..2N]所有元素的和是SUM。
	模仿动态规划解0-1背包问题的策略，令S(k, i)表示前k个元素中任意i个元素的和的集合。
	显然：
	S(k, 1) = {A[i] | 1<= i <= k}
	S(k, k) = {A[1]+A[2]+…+A[k]}
	S(k, i) = S(k-1, i) U {A[k] + x | x属于S(k-1, i-1) }*/
	public static void splitArr(int len, int[] a) {
		int sum = 0;
		for (int i = 0; i < len; i++) {
			sum += a[i];
		}
		int n = len / 2;
		// d[j][k]任意的j个数，且这些数之和为k的取法是否存在
		boolean[][] d = new boolean[len + 1][sum / 2 + 1];
		d[0][0] = true;
		for (int i = 0; i < len; i++) {
			for (int j = Math.min(i, n); j >= 1; j--) { //因為最多分割成n的大小
				for (int k = 0; k <= sum / 2; k++) {
					if (k >= a[i] && d[j - 1][k - a[i]]) {
						d[j][k] = true;
					}
				}
			}
		}
		for (int i = sum / 2; i >= 0; i--) {
			if (d[n][i]) {
				System.out.println("the splited sum is:" + i);
				break;
			}
		}
	}
}

	
	

		package com.wangyi;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 我的想法是：输入2n个数之后，对其整体排序。然后把它分成两个数组存储，
	

	

		    要是两组数据的和相差最小，
 * 那么可以等价到两个数组的对应位置上的连续两队数的差值最小，
 * 如：num1[j] = number[i];//选出的数据
				num2[j] = number[i + 1];//留下的数据
				if (j + 1 < n && i + 2 < number.length && i + 3 < number.length) {
					num2[j + 1] = number[i + 2];
					num1[j + 1] = number[i + 3];
 *具体例子：n = 5,2n = 10，随便输入10个数： 2 3 9 6 8 5 1 7 4 0；
 *排序后在分组：num1[] = {0,3,4,7,8}
 *			   num2[] = {1,2,5,6,9}
 *即：i = 0时，num1[i] >  num2[i];i = 1时；num1[i] < num2[i];i = 2时,
	

	

		    又是num1[i] > num2[i];i = 3 时，num1[i] < num2[i];
 *一直这么交替反复下去，利用小部分的“中和”使得最后的差最小 
 *
 *
 *在下第一次写，还望各位大神多多批评指正，谢谢了。
 */
public class Test1 {
	static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int[] number = new int[2 * n];
		for(int i = 0; i < number.length; i++){
			number[i] = sc.nextInt();
		}
		funcyion(number);
	}

	private static void funcyion(int[] number) {
		Arrays.sort(number);
		for (int i = 0; i < number.length; i++) {
			System.out.print(number[i] + " ");
		}
		int sum1 = 0;
		int sum2 = 0;
		int[] num1 = new int[n];
		int[] num2 = new int[n];
		int j = 0;
		for(int i = 0; i < number.length; i = i + 4){
				num1[j] = number[i];//选出的数据
				num2[j] = number[i + 1];//留下的数据
				if (j + 1 < n && i + 2 < number.length && i + 3 < number.length) {
					num2[j + 1] = number[i + 2];
					num1[j + 1] = number[i + 3];
					j = j + 2;
				}
				
		}
//		System.out.print("\nnum1[] =");
		for(int i = 0; i < n; i++){
//			System.out.print(" " + num1[i]);
			sum1 += num1[i];
		}
//		System.out.println();
//		System.out.printf("\nnum2[] =");
		for(int i = 0; i < n; i++){
//			System.out.print(" " + num2[i]);
			sum2 += num2[i];
		}
		System.out.printf("\n%d",sum1 - sum2);
	}
}
	

	

		
	

/*
*程序我已经测试很多次了可以正确分组。
*我考场上写了两个算法可惜太多情况情况没有考虑到。
*这样写算法不复杂，还可以得到正确结果，个人觉得算法可行。
*大家给的答案我测试了，除了JamesNiu给的我没有完全弄清楚，其他的都是错的。
*希望大家相互学习
*/
package number.action;

import java.util.Arrays;
import java.util.Scanner;
/*
 * @author snow
 * @time 2016-08-01
 * @网易笔试题
 */

public class NumerDivide_002 {
    public   static   void  main(String[] args) {  
    	int sum = 0;
    	int allNum[] = getArray();
        for(int p:allNum){
        	sum = sum +p;
        }
        System.out.println("数组中所有的整数和为："+ sum);
        System.out.println("挑选出来的数组为："+ Arrays.toString(divideArray(allNum,allNum.length)));  
    }  
    public static int[] divideArray(int[] allNum,int length){
    	int subLen = length/2;
    	int[] aNum = new int[subLen];
    	int[] bNum = new int[subLen];
    	subLen --;
    	length--;
    	Arrays.sort(allNum);  //数组排序
    	if(length<2)
    		return null;
    	else if(length==2){
    		aNum[0] = allNum[0];
    	}else{
    		bNum[subLen] = allNum[length];
    		int bSum = bNum[subLen];
    		aNum[subLen] = allNum[length-1];
    		int aSum = aNum[subLen];
    		int aLen = subLen-1,bLen = subLen -1;
    		for(int i=length-2;i>=0;i--){
    			if(aLen<0){
    				System.out.println("选出的数组和为"+aSum);
    				return aNum;
    			}else if(bLen<0){
    				for(int j=i;j>=0;j--){
    					aNum[aLen] = allNum[j];
            			aSum = aSum + aNum[aLen];
            			aLen -- ;
    				}
    				System.out.println("选出的数组和为"+aSum);
    				return aNum;
    			}
        		if(bSum>=aSum){
        			aNum[aLen] = allNum[i];
        			aSum = aSum + aNum[aLen];
        			aLen -- ;
        		}else{
        			bNum[bLen] = allNum[i];
        			bSum = bSum + bNum[bLen];
        			bLen --;
        		}
        	}
        	
    	}

		return aNum;
    }
    //输入的数据
    private static int[] getArray() {
    	System.out.println("请输入一个正整数以您要分割的数组长度");
        Scanner cin = new Scanner(System.in);
        int num = cin.nextInt();
        System.out.println("请输入"+num+"个整数");
        int i = 0;
        int[] nums = new int[num];
        while (i < num)
        {
            nums[i] = cin.nextInt();
            i++;
        }
        cin.close();
        return nums;
	}
    
    
	}

import java.util.Arrays;
import java.util.Scanner;

public class Main {


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();

        int[] input = new int[num];
        for (int i=0;i<num;i++){
            input[i] = scanner.nextInt();
        }

        if(num == 2 ){
            System.out.println("最小差值为: "+ Math.abs(input[1]-input[2]));
            return;
        }

        // 排序
        Arrays.sort(input);

        int[] num1 =new int[num/2];
        int[] num2 =new int[num/2];

        // 第一个数组那一个最小的，再拿一个最大的
        // 第二个数组拿一个次小的，在拿一个次大的
        int i=0;
        while(i<num){

            int j=0;
            int k=0;
            num1[j++] = input[i];
            num1[j++] = input[input.length-i-1];
            num2[k++] = input[i+1];
            num2[k++] = input[input.length-i-1-1];
            i+=4;
        }

        int sum1 = 0;
        int sum2 = 0;
        for(int n=0;n<num1.length;n++){
            sum1+=num1[n];
            sum2+=num2[n];
        }

        System.out.println("最小差值为: "+ Math.abs(sum1-sum2));

    }


}

//    要用回溯
    public static void main(String []args)
    {
        Scanner sr = new Scanner(System.in);
        int N = sr.nextInt();
        int []arr = new int[N*2];
        int sum = 0;
        for(int i=0;i<N*2;i++)
        {
            arr[i] = sr.nextInt();
            sum+=arr[i];
        }
        System.out.println(sum);
        //类似于叠高塔问题。N个砖头，叠两堆和的差最小的两堆塔。
        int [][] dp = new int[N+1][sum/2+2];
        for (int i = 0 ; i <= 2*N-1 ; ++i)  //2N个元素 0——2N-1
        {
            for (int j = Math.min(i,N) ; j >= 1 ; --j)  //i 从1 开始，i<=N时，j等于i 。i>N时候，j等于N
            {
                for (int s = sum/2+1 ; s >= arr[i] ; --s)  //总共有2N个元素，所以要进行2N次
                {
                    dp[j][s] = Math.max(dp[j-1][s-arr[i]]+arr[i] , dp[j][s]);
                }
            }
        }
        System.out.println(dp[N][sum/2+1]);
    }

	import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;



	public class Main {



	 public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  int m = scanner.nextInt(); //输入的数据数2n
  List<Integer> ls = new ArrayList<Integer>();
  for(int i = 0 ; i < m ; i ++){
   ls.add(scanner.nextInt()); //从键盘接收数据
  }
  Collections.sort(ls);   //按从小到大排序
  int suma = 0;
  String a = "";
  int sumb = 0;
  String b = "";
  for(int i = 0 ; i < ls.size()-1; i = i+2){
   if(suma + ls.get(i) < suma + ls.get(i+1)){
    suma += ls.get(i);
    a = a + ls.get(i)+" ";
    sumb += ls.get(i+1);
    b = b + ls.get(i+1)+" ";
   }else{
    sumb += ls.get(i);
    b = b + ls.get(i)+" ";
    suma += ls.get(i+1);
    a = a + ls.get(i+1)+" ";
   }
  }
  System.out.println("第一组数：" + a +"总和"+ suma);
  System.out.println("第一组数：" + b +"总和"+ sumb);
 }
 



	}

import java.util.Arrays;
import java.util.Scanner;

public class Main {     public static void main(String args[]) {         Scanner in = new Scanner(System.in);         int n = in.nextInt();         int[] num = new int[n];         int[] num1 = new int[n / 2];         int[] num2 = new int[n / 2];         for (int i = 0; i < n; i++) {             num[i] = in.nextInt();         }         Arrays.sort(num);         int a = 0, b = 0, sumA = 0, sumB = 0;         for (int i = 0; i < n; i++) {             if (i % 2 == 0) {                 num2[a++] = num[i];                 sumB += num[i];             } else {                 num1[b++] = num[i];                 sumA += num[i];             }         }         System.out.println("差最小为：" + Math.abs(sumA - sumB));     }
}

	

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main{

	/**
	 * 任意2n个整数，从其中选出n个整数，
	 * 使得选出的n个整数和同剩下的n个整数之和的差最小。
	 */
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int n = scanner.nextInt();
		int[] data =new int[2*n];
		int temp=0,sum=0;
		for(int i=0;i<2*n;++i){
			temp=scanner.nextInt();
			data[i]=temp;
			sum+=temp;
		}
	//	System.out.println("sum="+sum);
		Arrays.sort(data);
//		for(int i=0;i<2*n;++i){
//			System.out.print(" "+data[i]);
//		}
		//System.out.println();
		int mid=sum/2;
		int choose_sum = 0;
		//从最大的开始遍历，找出选出的数之和离sum/2最近，
		//只要加上当前数，比sum/2，则就可以加，否则当前数不加，往下遍历，
		for(int i=2*n-1;i>=0;--i){
			choose_sum += data[i];
			if(choose_sum>mid){
				if(i==2*n-1){
					System.out.println(" "+data[i]);
			//		System.out.println("最开始就选中最佳了");
					break;
				}
				choose_sum -= data[i];
				continue;
			}else if(choose_sum==mid){
				System.out.println(" "+data[i]);
			//	System.out.println("选到最佳的");
				break;
			}
			System.out.print(" "+data[i]);
		}
		System.out.println("\n选中的之和为："+choose_sum);
	}

}

public class Main { // 题目：任意2n个整数，从其中选出n个整数，使得选出的n个整数和同剩下的n个整数之和的差最小。 public static void main(String[] args) { int A[] = { 1, 2, 3, 5, 7, 8, 9 }; // int A[] = { 1, 5, 7, 8, 9, 6, 3, 11, 20, 17 }; func(A);
    } static void func(int A[]) { int i; int j; // 下面的变量声明地很直白，不解释 int n2 = A.length; int n = n2 / 2; int sum = 0; // 计算数组总和 for (i = 0; i < A.length; i++) {
            sum += A[i];
        } /*还记得编程之美中的话吗？
        我们的程序不需要按照上述递推公式计算每个集合，只需要为每个集合设一个标志数组，标记SUM/2到1这个区间中的哪些值可以被计算出来。
        flag[i][j]:任意i个整数之和是j,则flag[i][j]为true。换言之，flag[i][j]为true，那么一定能找到一组整数，使它们的和是j。
        下面的代码将对flag数组进行初始化*/ boolean flag[][] = new boolean[A.length + 1][sum / 2 + 1]; for (i = 0; i < A.length; i++) for (j = 0; j < sum / 2 + 1; j++)
                flag[i][j] = false;

        flag[0][0] = true; // 重点来了 for (int k = 0; k < n2; k++) { //i取k和n中的较小值，我们的目的是找出集合S(2N, N)中与SUM最接近的那个和，所以k>n时，取到n就足够了。k<n时，我们显然无法从3个数中任意选择4个数，所以取k值 for (i = k > n ? n : k; i >= 1; i--) { // 两层外循环是遍历集合S(k,i)，遍历顺序S[1][1],S[2][2],S[2][1],S[3][3]……特殊的依赖关系导致必须这样设计算法 // 内层循环计算将A[k]加入到集合中能取到的可能的j值 for (j = 0; j <= sum / 2; j++) {//j是i个任意整数可能的和，从0遍历到sum / 2，判断能否得到 // 得到j值的条件，j是和，A[k]只是其中一个，肯定需要j >= A[k]，否则，取flag[i - 1][j - A[k]]的值的时候会发生越界情况。flag[i - 1][j - A[k]] = true代表可以找到i - 1个数，使它们的和为j - A[k]，所以此条件满足时意味着flag[i][j] = true if (j >= A[k] && flag[i - 1][j - A[k]])
                        flag[i][j] = true;
                }
            }
        } // 终于计算完了，现在找到最合适的结果就好了，要找到最接近SUM / 2的和，倒着找最好了 for (j = sum / 2; j >= 0; j--) { if (flag[n][j]) {
                System.out.println("sum is " + sum);
                System.out.println("sum/2 is " + sum / 2);
                System.out.println("j is " + j);
                System.out.println("minimum delta is " + Math.abs(2 * j - sum)); break;
            }
        }
    }
}