| | | |
|
Задача о рюкзаке с восстановлением ответа
Задача о рюкзаке
Дано 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, если набрать данный вес невозможно.
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 |
| |
![]()
|
|
Копилка
Задача о рюкзаке
Задан вес 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. |
| |
![]()
|
|
Гомер Симпсон
Задача о рюкзаке
Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.
Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.
Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.
Выходные данные
Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остаётся какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остаётся как можно меньше.
| Ввод |
Вывод |
| 1 2 1000 |
1000 |
| 2 1 1000 |
1000 |
| |
![]()
|