정수 배열 2 짝수 합계

Question

이 프로그래밍 문제를 해결하기가 어렵습니다. 크기가 N 일 수있는 정수 배열을 사용해야합니다. 2 <= N <= 30입니다. 나는 배열이 합이 같은 두 개의 더 작은 배열로 나눌 필요가있다. 그리고 만약 그것들이 같지 않다면 같은 값에 가능한 가깝게 될 필요가있다. 필자는 일종의 재귀 함수를 사용하는 것이이 상황에서 이상적이라고 생각하지만 그렇지 않다면 동적으로 프로그래밍 된 솔루션도 제대로 작동합니다.

Answer 1

wikipedia article on Partition problem을 검토 할 것입니다. 당신이 다항식 시간에이 문제를 해결할 수 있다면 당신이 정말로 유명한 될 것

public static bool BalancePartition(int[] S) 
{ 
    int n = S.Length; 
    int N = S.Sum(); 
    bool[,] P = new bool[N/2 + 1, n + 1]; 

    for (int i = 0; i < n + 1; i++) 
     P[0, i] = true; 

    for (int i = 1; i <= N/2; i++) 
     for (int j = 1; j <= n; j++) 
      if (S[j - 1] <= i) 
       P[i, j] = P[i, j - 1] || P[i - S[j - 1], j - 1]; 
      else 
       P[i, j] = P[i, j - 1]; 

    return P[N/2, n]; 
}