1
균형 파티션 :. 0 ... K의 범위에있는 n 개의 정수 집합을가집니다.이 정수를 두 개의 하위 집합으로 분할하여 | S1 - S2 |를 최소화합니다. 여기서 S1과 S2는 두 개의 하위 집합 각각에있는 요소의 합계를 나타냅니다. 배낭 문제 : 각 가중치와 값이있는 항목 집합이 주어지면 총 가중치가 주어진 제한보다 작거나 같고 총 값이 큰 컬렉션에 포함 할 각 항목의 수를 결정합니다 가능한 한. 같은 개체를 두 번 사용할 수 없습니다.균형 파티션 대 배낭 1/0 복잡도
균형 잡힌 파티션 문제에 대한 해답은 배낭 크기 S에 대한 배낭 알고리즘을 적용하는 것입니다. 여기서 S는 모든 입력 숫자의 합계이고 가중치는 각 개체. 여전히 here은 배낭 문제가 O (nC)이고 균형 분할 문제가 O (n^2 k)라고 말합니다. 내가 뭘 놓치고 있니?