將數組分成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,]