Олимпиадный тренинг

Задача . Задача о рюкзаке с восстановлением ответа


Задача

Темы: Задача о рюкзаке
Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно. 
Ими наполняют рюкзак, который выдерживает вес не более M. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.
 
Входные данные: 
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;
- во второй строке вводятся N натуральных чисел mi, не превышающих 100;
- в третьей строке вводятся N натуральных чисел сi, не превышающих 100.
 
Выходные данные: выведите номера предметов (числа от 1 до N), которые войдут в рюкзак наибольшей стоимости (по одному номеру в строке).
 

 

Примеры
Входные данные Выходные данные
1
4 6
2 4 1 2
7 2 5 1
1
3
4

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6487
C#1
Java6
Python166
Комментарий учителя