배열을 3 개 세트로 나누기

Question

정수 배열을 사용하면 배열을 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

조언을 수있는 것은 무차별 자바 사용할 수있는 솔루션 노트입니다 -이 솔루션의 복잡성은 O입니다

/** 
* 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); 
} 

샘플 출력 매우 매우 느립니다 (3^N) :

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