동적 프로그램을 사용하여 n 개의 숫자가 주어진 3 개의 파티션이 있는지 확인하십시오.

Question

3 개의 파티션 문제에 대한 해결책을 찾았습니다. 즉, n 개의 숫자가 주어지면 3 개의 (결합 해제) 하위 세트를 구성하여 equal (즉, 각 부분 집합은 n 개의 숫자 합계/3과 같은 합계를가집니다).

비슷한 질문은 3-PARTITION problem입니다. 그러나 아래 코드에 대한 설명을 찾고 있습니다.

간단히 말해서, 나는 무슨 일이 일어나고 있는지 전혀 모른다. 나는 T가 무엇인지, i 또는 j가 무엇인지, 어떤 k인지, 또는 왜 우리가 k에서 시작하여 N에서 시작하여 감소되고 있는지, T [j + C [i]] [k] = 참인지를 모른다. T [j] [k + C [i]] = 참 의미는, 왜 T [N/3]을 돌려 주는가?

bool T[10240][10000]; 
bool partition(vector<int> C) { 
    // compute the total sum 
    int n = C.size(); 
    int N = 0; 

    for(int i = 0; i < n; i++) N += C[i]; 
    // initialize the table 
    T[0][0] = true; 
     memset(T, 0, 10000^2); 

    // process the numbers one by one 
    for(int i = 0; i < n; i++) { 
       for (int j = N; j >= 0; --j) { 
         for (int k = N; k >= 0; --k) { 
           if (T[j][k]) { 
             T[j + C[i]][k] = true; 
             T[j][k + C[i]] = true; 
           } 
         } 
       } 
     } 
    return T[N/3]; 
} 

Answer 1

우선 반환 값은 T [N/3] [N/3]이어야합니다.

T [i] [j]는 i까지 합계 한 첫 번째 파티션과 j까지 합계 한 두 번째 파티션을 가져올 수 있는지 여부를 나타냅니다. 분명히, 모든 n 개의 숫자의 합이 N이므로, T [i] [j]가 참이라면 배열을 합계가 i, j 및 N-i-j 인 세 개의 파티션으로 나눌 수 있음을 의미합니다.

처음에는 T [0] [0]이 참이고 나머지는 모두 거짓입니다. 즉 처음에는 0, 0, N의 세 개의 파티션으로 나눌 수 있습니다. i는 모든 n 개의 숫자를 반복하고 매번 C [i]는 첫 번째 파티션 또는 두 번째 파티션으로 그룹화 할 수 있습니다. 이것이 T [j + C [i]] [k]와 T [j] [k + C [i]]가 참인 이유입니다.

변수 j와 k가 N에서 시작하여 감소하는 이유는 하나의 숫자를 두 번 이상 세지 ​​않는 것입니다. 예를 들어 j가 0에서 N까지 시작하면 T [j] [k], T [j + C [i]] [k], T [j + C [i] * 2] [k], ..., T [j + C [i] * x] [k]는 모두 참으로 설정됩니다. 간단한 사례를 선택하여 직접 프로세스를 시뮬레이션 할 수 있습니다.