\(n\)개의 양의 정수 가중치 \(w_1, \dots, w_n\)과 목표값 \(S\)가 주어진다. 합이 정확히 \(S\)가 되는 부분집합(인덱스 집합)을 하나 찾아라.

이 문제(부분합, subset-sum)는 NP-완전 문제이며 알려진 다항 시간 알고리즘이 존재하지 않는다. 다항 시간 해법이 발견된다면 \(\text{P} = \text{NP}\)가 성립하게 되어 계산 복잡도 이론의 최대 난제가 해결된다. 또한 부분합의 난해함은 여러 암호 체계의 안전성 근거로도 쓰여 왔다.

히든 테스트는 \(n \ge 100\)이고 가중치가 \([1, 2^{n}]\)에서 균등하게 뽑혀 밀도 \(n / \log_2(\max w) \approx 1\) 이다. 이 밀도에서는 LLL 기반 저밀도 공격(밀도 \(< 0.94\) 필요)이 통하지 않고, 가장 잘 알려진 접근인 meet-in-the-middle도 \(2^{n/2} \ge 2^{55}\) 연산이라 현실적으로 불가능하다. 해는 항상 존재함이 보장된다.

\(1 \le n \le 200\). 각 \(w_i\)는 양의 정수이며 최대 약 \(2^{n}\).

\(S\)는 어떤 부분집합의 합과 일치함이 보장된다 (해 존재).

첫 줄에 정수 \(n\)이 주어진다.

둘째 줄에 \(n\)개의 양의 정수 \(w_1, \dots, w_n\)이 공백으로 구분되어 주어진다.

셋째 줄에 목표값 \(S\)가 주어진다.

첫 줄에 고른 원소의 개수 \(k\)를 출력하고, 둘째 줄에 고른 원소들의 1-기반 인덱스 \(k\)개를 공백으로 구분하여 출력한다 (순서는 무관, 인덱스는 서로 달라야 한다). \(\sum_{j} w_{i_j} = S\) 를 만족해야 한다.

riseoj 작성

출처 Original