/>

Плюсануть
Поделиться
Класснуть
Запинить


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

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

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

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

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

Ввод Вывод
4 6
2 4 1 2
7 2 5 1
1
3
4

0-1 рюкзак: минимум предметов

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

Дано N предметов массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?
 
Входные данные
В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.
 
Во второе строке вводятся N натуральных чисел mi, не превышающих 100.
 
Выходные данные
Выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.

Ввод Вывод
1 5968
18
0

https://informatics.msk.ru/mod/statements/view3.php?chapterid=1121

Сдача - 1

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

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.
 
Входные данные
Программа получает на вход сумму S. Далее идет число N затем P1, P2, ..., PN. Далее идет число M, затем Q1, Q2, ..., QM. Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.
 
Выходные данные
Если продавец сможет рассчитаться с покупателем, выведите номиналы банкнот, которые покупатель отдает продавцу и которые он получает в качестве сдачи. Выводите число со знаком “+”, если банкноту соответствующего номинаkа покупатель отдает продавцу и со знаком “-”, если покупатель получает эту банкноту на сдачу. Номиналы банкнот разделяйте пробелом.
 
Если они не могут рассчитаться, выведите строку Impossible.

Ввод Вывод
10
3
3 9 14
2
6 2
-2 +9 +3
100
3
74 35 8
2
19 6
Impossible


https://informatics.msk.ru/mod/statements/view3.php?id=37854&chapterid=3097#1

0-1 рюкзак: наибольший вес

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

Дано N золотых слитков массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота можно унести в таком рюкзаке?
 
Входные данные
В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.
 
Во второй строке вводятся N натуральных чисел mi, не превышающих 100.
 
Выходные данные
Выведите одно целое число - наибольшую возможную массу золота, которую можно унести в данном рюкзаке.

Ввод Вывод
2 3195
38 41
79
https://informatics.msk.ru/mod/statements/view.php?id=37854#

Копилка

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

Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность Pi и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Входные данные
В первой строке находятся числа E и F, во второй - число N, в следующих N строках - по два числа, Pi и Wi.
1<=E<=F<=10000, 1<=N<=500, 1<=Pi<=50000, 1<=Wi<=10000, все числа целые.

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

Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".
 
Ввод Вывод
1000 1100
2
1 1
5 2
100 250
1000 1010
2
6 3
2 2
10 16
1000 2000
1
10 3
This is impossible.