Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 51%)

Одной из классических NP-полных задач является так называемая «Задача о рюкзаке». Формулируется она следующим образом. Дано n предметов, каждый из которых характеризуется весом wi и полезностью pi. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал W, а суммарная полезность была максимальна.

Ваша задача состоит в том, чтобы написать программу, решающую задачу о рюкзаке.

Входные данные

Первая строка входного файла INPUT.TXT содержит натуральные числа n (1 ≤ n ≤ 20) и W (1 ≤ W ≤ 109). Каждая из последующих n строк содержит описание одного предмета. Каждое описание состоит из двух чисел: wi – веса предмета и pi – его полезности (1 ≤ wi, pi ≤ 109).

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите количество выбранных предметов и их суммарную полезность. Во второй строке выведите через пробел их номера в возрастающем порядке (предметы нумеруются с единицы в порядке, в котором они перечислены во входном файле).

Если искомых наборов несколько, выберите тот, в котором наименьшее число предметов. Если же после этого ответ по-прежнему неоднозначен, выберите тот набор, в котором первый предмет имеет наименьший возможный номер, из всех таких выберите тот, в котором второй предмет имеет наименьший возможный номер, и т.д.

Примеры

INPUT.TXTOUTPUT.TXT
12 10
10 100
9 80
1 100
1
25 100
80 1000
50 550
50 550
50 550
50 550
2 1100
2 3
3 6 100
80 1000
50 550
50 550
50 550
50 550
100 1100
1 1100
6

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Условный оператор
 Операторы цикла
 Строковые типы данных
 Массивы
 Функции
 Сортировка
 Двумерные массивы
 Рекурсия
 Рекурсия - 1
 Рекурсия - 2
 A. Разворот
 B. Числа Фибоначчи
 C. Перестановки
 D. Функция - 2
 E. Формула
 F. Задача о рюкзаке
 G. Сумма двух чисел
 H. Раскраска карты

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru