배낭 문제

배낭 문제는 다음과 같이 정의된다. $n$개의 물건이 있고, $i$번째 물건의 무게는 $w\_i$, 가치는 $v\_i$이다. 물건의 무게 합이 배낭의 용량 $c$를 넘지 않도록 물건을 골라 가치의 합이 최대가 되는 집합을 구한다. 배낭 문제는 NP-난해하지만, 물건 무게의 총합에 비례하는 시간에 동적 계획법으로 풀 수 있다.

그러나 일부 경우에는 배낭 문제를 탐욕법으로 풀 수 있다. 그중 하나는 배낭 문제의 인스턴스가 매트로이드를 이루는 경우이다.

매트로이드는 순서쌍 $\langle X, {\cal I}\rangle$이다. $X$는 유한 집합이고, $\cal I$는 $X$의 부분집합들로 이루어진 족이다. $\cal I$의 원소를 독립 집합이라고 부른다. $\cal I$는 다음 공리를 만족해야 한다.

1. ${\cal I} \ne \varnothing$;
2. $A \in {\cal I}$이고 $B \subset A$이면, $B \in {\cal I}$이다;
3. $A, B \in {\cal I}$이고 $|A| > |B|$이면, $x \in A \setminus B$인 $x$가 존재하여 $B \cup \{x\}\in{\cal I}$이다.

여기서 $|A|$는 집합 $A$에 속한 물건의 개수이다.

매트로이드의 예로, 무방향 그래프의 간선 집합을 들 수 있다. 간선 집합에 사이클이 없으면 독립 집합이다.

물건들의 무게가 $w\_1, w\_2, \ldots, w\_n$이고, 이 물건 전체를 $X$로 둔다. 물건 번호의 집합 $\{i\_1, i\_2, \ldots, i\_k\}$은 $w\_{i\_1}+w\_{i\_2}+\ldots+w\_{i\_k} \le c$를 만족하면 독립 집합이라고 한다. 주어진 $w\_1, w\_2, \ldots, w\_n$과 $c$에 대해 이 구성이 매트로이드를 이루는지 판정한다.

첫 줄에 정수 $n$ ($1 \le n \le 50$)이 주어진다. 둘째 줄에는 정수 $w\_1, w\_2, \ldots, w\_n$ ($1 \le w\_i \le 100$)이 주어진다. 셋째 줄에는 정수 $c$ ($\max w\_i \le c \le \sum w\_i$)가 주어진다.

배낭 문제의 해의 집합이 매트로이드를 이루면 YES를, 그렇지 않으면 NO를 출력한다.

그렇지 않은 경우에는 둘째 줄에 위배되는 공리의 번호를 정수 하나로 출력한다. 공리 2 또는 공리 3이 위배되면, 다음 두 줄에 공리가 성립하지 않는 집합 $A$와 $B$를 출력한다. 각 집합은 물건의 개수를 먼저 쓰고, 그 뒤에 물건 번호들을 쓴다.