PartitionProblem variation - 부분 집합의 고정 크기

Question

NP가 완료된 파티션 문제의 변형 인 문제가 있습니다. 이것은 최적화 문제이며 의사 결정 문제는 아닙니다.

문제 : 합계의 차이가 최소가되도록 두 개의 하위 집합으로 숫자 목록을 분할하고 두 개의 하위 집합을 찾습니다. n이라도 맞으면 크기는 n/2이어야하며 이상한 경우 floor[n/2] 및 ceil[n/2]이어야합니다.

의사 다항식 시간 DP 알고리즘이 정확한 솔루션에 가장 적합하다고 가정하면 어떻게 해결할 수 있습니까? 그리고 무엇이 가장 좋은 알고리즘을 해결할 것입니까?

Answer 1

사용되는 알고리즘을 지정하지 않았기 때문에 난 당신이 여기에 정의 된 하나를 사용하는 가정합니다 : (N에 초기화, 그리고 http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp3.pdf

이 알고리즘을 사용하면 최상의 결과를 추적하는 변수를 추가를 한 세트를 항상 빈 세트로 가져올 수 있으므로 목록의 모든 숫자의 합계)와 T (예 : T [i] = true)을 업데이트 할 때마다 bestRes = abs(i-n/2)<bestRes : abs(i-n/2) : bestRes과 같은 작업을 수행합니다. 그리고 bestRes을 반환합니다. 물론 알고리즘의 복잡성은 변하지 않습니다.

두 번째 질문에 대해 알지 못합니다.