2의 거듭 제곱에 대해 세트 분할을위한 다항식 시간 알고리즘?

Question

프로그래밍/구현보다 알고리즘/증명 문제가 훨씬 더 많으므로 StackOverflow가 적합한 곳이 아니라면 사과드립니다. 이 문제에 관해서는

:

는 우리가 숫자의 집합을 가지고 있다고 가정하고, 모든 수는 양의 정수와 2의 전력해야합니다. 예를 들어 {1, 1, 2, 4, 8, 8, 8, 8, 128} 일 가능성이 있습니다. 집합을 A 및 B으로 분할하려는 경우 모든 요소는 정확히 A 또는 B이어야하며 A의 요소 합계는 B의 요소 합계와 같습니다. 항상 중 하나

• 더도 분할이 존재하지 않는 수를 결정, 또는 A에
• 반환 파티션과 금액이 동일하다는 B 같은 것이 상황에 대한 다항식 시간 알고리즘이 있습니까?

물론 다항식 시간 알고리즘이 없다면 그 증명을위한 몇 가지 방향을 알고 싶습니다 (즉, 다른 NP 어려운 문제와 동등 함을 보여줌으로써).

은 내가 도울 수있는 몇 가지 문제가 있다는 것을 알고, 문맥, 나는 여기에 요약됩니다 :

1. 설정 파티션은 NP-어렵다. set-partition에는 임의의 숫자 집합이 있습니다. 해결책은 파티션 A와 B입니다. 여기서 각 요소는 정확히 A 또는 B이므로 sum(A) = sum(B)입니다.
2. 부분 집합 합계는 NP 하드입니다. subset-sum에는 임의의 숫자 집합이 있습니다. 해는이 집합의 부분 집합이므로 그 집합의 요소의 합은 원하는 수 x와 같습니다.

도움을 주시면 대단히 감사하겠습니다. 감사!

Answer 1

이 방법을 보는 한 가지 방법은 제공된 숫자의 합계로 총/2 인 대상 숫자를 표현하려고하는 것입니다. 이것은 정말로 변화를 만드는 것의 문제입니다.

다음은 유용한 보조 정리입니다. 값이 모두 2 진수 인 값이 < = 2^k 인 동전이있는 경우 정확하게 2^k를 만들거나 큰 숫자를 만들 수 없으며, 또는 2^k보다 큰. 이것을 보시려면 동전을 모두 가져 가세요. 동일한 가치의 동전이 두 개 이상있는 경우 동전을 다 쓰거나 2^k에 도달 할 때까지 두 개의 동전을 함께 붙여서 다음으로 높은 값의 동전을 만드십시오. 2^k에 도달하면 끝납니다. 너가 다 떨어지면, 너는 여전히 2의 멱수이고, 모두 2^k보다 작고, 다른 값 하나당 하나 인 다양한 값의 하나의 동전들의 집합을 가지며, 결과는 2^k -1.

목표 값을 변경하려면 숫자를 동전으로 취급하고 지금까지 가지고있는 값과 목표 값 사이의 차이보다 더 큰 최대 동전을 반복적으로 사용하십시오.

목표 값에 도달하면 문제가 해결됩니다. 그렇지 않다면 옳은 대답을 놓치셨습니까? 당신은 가장 큰 가치의 동전으로 시작했습니다. 당신의 첫번째 실수를 찾으십시오 - 당신은 크기가 2^k 인 동전을 가져 왔고 크기 2^k의이 동전을 포함하지 않은 나머지 합계를 보충 할 방법이 있습니다. 그러나이 마법 방법은 2^k보다 큰 값의 동전을 사용하여 2^k 이상 변화를 만드는 방법입니다.그래서이 올바른 대답의 어딘가에 정확히 2^k까지 더하는 동전이 있습니다. 이 정답을 취하여 2^k까지 합친 동전을 제거하고 사용했던 2^k에 대해 동전으로 바꾼다. 그러면 다른 올바른 답을 얻게된다. 그래서 당신은 모든 것이 바로 끝났고 어떤 해결책을 얻을 수 있다면 목표 값까지의 거리보다 작은 최대 동전 (수)을 반복적으로 사용하여 얻으십시오.

위력 검사 - http://cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf에 주어진 부분 집합 합계에 대한 감축을 살펴보면 2의 정확한 제곱 수가 아닌 숫자가 필요하다는 것을 알 수 있으므로 여기서 제안한 것은 숫자가 2의 제곱 수인 경우에만 작동하는 것으로 판명되었습니다. 다항식 시간에 NP 완전 문제를 푸는 것으로 주장하지 않습니다.