n个数分为两组，两组数的个数尽可能相等，差值最小

发布时间：2020-12-14 04:46:46 所属栏目：百科来源：网络整理

导读：题目描述：对于有n个数的数组，分为两组，这两组的数的个数尽可能相等（不超过1），同时两组的数之和的差值最

题目描述：对于有n个数的数组，分为两组，这两组的数的个数尽可能相等（不超过1），同时两组的数之和的差值最小。

这个题目使用类似0-1背包问题，思路：从k个数中选i个数，求所有可能的和，并把这些和放在flag中用true表示。（k,i,flag见代码）

 1 public static void main(String[] args){
 2         int[] arr = {1,2,3,5,7,8,9};
 3         int n = 7;
 4         int sum = 0 5         for(int i:arr){
 6             sum += i;
 7         }
 8         boolean[][] flag = new boolean[n/2+1][sum/2+1];
 9         int i=0;i<n/2+1;i++){
10             int j=0;j<sum/2+1;j++11                 flag[i][j] = false12             }
13 14         flag[0][0] = true15         int k = 0;k<n;k++16             int i=k>n/2?n/2:k;i>=1;i--17                 //遍历s(k,i)
18                 int j=0;j<=sum/2;j++19                     if(j>=arr[k]&&flag[i-1][j-arr[k]]){
20                         flag[i][j] = 21                     }
22                 }
23 24 25         int i = sum/2;i>=0;i++26             if(flag[n/2][i]) {
27                 System.out.println(i);
28                 break29 30 31     }

我觉得比较难理解的地方就是flag[i-1]这一行是什么意思：代表从k中取i-1个数，他们的各种和的可能的体现（存在即为true）

最里面一层循环的意思是：从i-1这一行中取各种和然后加上arr[k]凑成i个数的和，体现在flag[i]里面。

第二层循环的意思是：执行1-i这么多行

最外面一层就是不断往里面加数。

我测试的例子不多，可能有遗漏的地方，请留言指出来，难以理解的地方也可以留言讨论。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!