将数组分成3组

Question

给定一个整数数组，将数组分成3组，将3组分成3组，使3组元素的和尽可能接近。

我的方法如下：

1. 排序从大到小的顺序
2. 阵列插入元件成组，其总和是最小的。

sort(a, a+n); 
int o = 0, tw = 0, th = 0; 

while(n--) 
{ 
    if (o <= tw && o <= th) 
    o += a[n]; 
    else if (tw <= o && tw <= th) 
    tw += a[n]; 
    else 
    th += a[n]; 
} 

谁能告诉我什么是错我的解决方案？或将建议一个更好的解决方案

Answer 1

这里是蛮力的Java解决方案，您可以使用，请注意 - 该解决方案的复杂度为O（3^N），这是非常非常慢

/** 
* Returns absolute difference between 3 values in array 
*/ 
static int getdiff(final int s[]) 
{ 
    return Math.abs(s[0] - s[1]) + Math.abs(s[1] - s[2]) + Math.abs(s[2] - s[0]); 
} 

/** 
* Calculates all possible sums and returns one where difference is minimal 
*/ 
static int[] getsums(final int a[], final int idx, final int[] s) 
{ 
    // no elements can be added to array, return original 
    if (idx >= a.length) 
     return s; 

    // calculate 3 different outcomes 
    final int[] s1 = getsums(a, idx + 1, new int[] {s[0] + a[idx], s[1], s[2]}); 
    final int[] s2 = getsums(a, idx + 1, new int[] {s[0], s[1] + a[idx], s[2]}); 
    final int[] s3 = getsums(a, idx + 1, new int[] {s[0], s[1], s[2] + a[idx]}); 

    // calculate difference 
    final int d1 = getdiff(s1); 
    final int d2 = getdiff(s2); 
    final int d3 = getdiff(s3); 

    if ((d1 <= d2) && (d1 <= d3)) 
     return s1; 
    else if ((d2 <= d1) && (d2 <= d3)) 
     return s2; 
    else 
     return s3; 
} 

static int[] getsums(final int a[]) 
{ 
    return getsums(a, 0, new int[] {0, 0, 0}); 
} 

static void printa(final int a[]) 
{ 
    System.out.print("["); 
    for (final int t : a) 
     System.out.print(t + ","); 
    System.out.println("]"); 
} 

static public void main(final String[] args) 
{ 
    final int a[] = new int[] {23, 6, 57, 35, 33, 15, 26, 12, 9, 61, 42, 27}; 

    final int[] c = getsums(a); 

    printa(a); 
    printa(c); 
} 

输出示例：

[23,6,57,35,33,15,26,12,9,61,42,27,] 
[115,116,115,]