问题：

给定一个数组，每个元素范围是0~K（K < 整数最大值2^32），将该数组分成两部分，使得 |S1- S2|最小，其中S1和S2分别是数组两部分的元素之和。

分析：

问题本质是01背包问题。

（1）每个元素值既是价值也是重量。

（2）背包承重上限为所有元素总和的一半；设为mid = sum/2。

（3）问题转化为寻找[0,mid]范围内的最大价值sum1。

（4）最后结果：|sum-2*sum1|，当sum1==mid时，获得最优解0.

（5）为了数据溢出错误使用double类型记录值，最后使用格式化输出整型结果。

代码：

 1 import java.util.*;
 2 
 3 /**
 4  * 背包问题
 5  * 假设背包承重上限为sum/2
 6  * 找出价值最接近sum/2的物品集合
 7  */
 8 public class Main{
 9     public static void main(String args[]){
10             Scanner in = new Scanner(System.in);
11             int n = in.nextInt();
12             double[] ar = new double[n];    //记录数据
13 
14             for(int i=0;i<n;i++){
15                 ar[i] = in.nextDouble();
16             }
17             double sum = Arrays.stream(ar).sum();
18             double midl = sum/2;
19             int maxw = (int)Math.ceil(midl);
20             double[] dp = new double[maxw+1];
21         //开始处理背包问题:提前结束条件->sumx = midel;
22             //初始化
23             for(int i=0;i<=maxw;i++){
24                 dp[i] = ar[0]<i?0:ar[0];
25             }
26             boolean flag=false;
27             double sum1 = ar[0];
28             for(int i=1;i<n && !flag;i++){
29                 //当元素大于midel，自动过滤
30                 for(int j=maxw;j>=ar[i];j--){
31                     int index = (int)(j-ar[i]);
32                     double tsum1 = dp[index]+ar[i]; //选择该元素
33                     if(tsum1==midl){
34                         flag=true;
35                         break;
36                     }
37                     if(tsum1<midl && tsum1>dp[j]){
38                         sum1 = tsum1;
39                         dp[j] = tsum1;
40                     }
41                 }
42             }
43        if(flag){
44            System.out.println(0);
45        }else{
46            System.out.printf("%.0f",Math.abs(sum-2*sum1));
47        }
48     }
49 }

View Code

集合划分问题

问题：

分析：

代码：

推荐阅读