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