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

Задачи из рубрикатора

Тег: Задача о рюкзаке

Условие задачи  
ID 33086: 0-1 рюкзак: наибольший вес
0-1 рюкзак: наибольший вес
Темы: Задача о рюкзаке   

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

 

Примеры
Входные данные Выходные данные
1
2 3195
38 41
79

ID 33105: Копилка
Копилка
Темы: Задача о рюкзаке   

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

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

Выходные данные: выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".

 
 

 

Примеры
Входные данные Выходные данные
1
1000 1100
2
1 1
5 2
100 250
2
1000 1010
2
6 3
2 2
10 16
3
1000 2000
1
10 3
This is impossible.

ID 33087: 0-1 рюкзак: минимум предметов
0-1 рюкзак: минимум предметов
Темы: Задача о рюкзаке   

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

 

Примеры
Входные данные Выходные данные
1
1 5968
18
0

ID 33088: Гирьки
Гирьки
Темы: Задача о рюкзаке   

Дан набор гирь массой1, …, mN. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?
 
Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100;
- во второе строке вводятся N натуральных чисел mi, не превышающих 100.
 
Выходные данные: выведите YES или NO.
 

 

Примеры
Входные данные Выходные данные
1 1
17
NO
2 2
19 19
YES

ID 33081: Задача о рюкзаке с восстановлением ответа
Задача о рюкзаке с восстановлением ответа
Темы: Задача о рюкзаке   

Дано 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

ID 33104: Сдача - 1
Сдача - 1
Темы: Задача о рюкзаке   

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

 

Примеры
Входные данные Выходные данные
1
10
3
3 9 14
2
6 2
-2 +9 +3
2
100
3
74 35 8
2
19 6
Impossible

ID 33650: Гомер Симпсон
Гомер Симпсон
Темы: Задача о рюкзаке   

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.

Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.

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

Ввод Вывод
1 2 1000 1000
2 1 1000 1000