NP задача о рюкзаке
Одной из классических NP-полных задач является так называемая Задача о рюкзаке. Формулируется она следующим образом.
Дано n предметов, каждый из которых характеризуется весом w[i] и полезностью p[i]. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал w, а суммарная полезность была максимальной.
Входные данные
Первая строка содержит натуральные числа n (1 ≤ n ≤ 20) и w (1 ≤ w ≤ 10^9). Далее идут n строк по два числа: вес i-го предмета w[i] и его полезность p[i] (1 ≤ w[i], p[i] ≤ 10^9).
Выходные данные
В первой строке выведите количество выбранных предметов и их суммарную полезность. Во второй строке выведите их номера в возрастающем порядке (предметы нумеруются с единицы в порядке, в котором они заданы на входе).
Если искомых наборов несколько, выберите тот, в котором наименьшее число предметов. Если же после этого ответ по-прежнему неоднозначен, выберите тот набор, в котором первый предмет имеет наименьший возможный номер, из всех таких вариантов выберите тот, в котором второй предмет имеет наименьший возможный номер, и т.д.