Задача о рюкзаке

Задача о рюкзаке формулируется следующим образом: дано $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$, такой что $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$). Вторая строка содержит $n$ целых чисел $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".

Во втором случае на второй строке выведите одно целое число --- номер аксиомы, которая нарушается. Если нарушается вторая или третья аксиома, то на следующих двух строках выведите описания множеств $A$ и $B$, для которых утверждение аксиомы не выполняется. Каждое множество описывается количеством предметов в нем, после чего должны следовать номера этих предметов.