Разбиение массива на 3 множества

Question

Учитывая массив целых чисел, разделите массив на 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,]