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


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


Условие задачи Прогресс
ID 33650. Гомер Симпсон
Темы: Задача о рюкзаке   

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

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

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

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

Ввод Вывод
1 2 1000 1000
2 1 1000 1000
3 6 1000 333 1

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

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

 

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

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

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

 

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

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 33105. Копилка
Темы: Задача о рюкзаке   

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

Входные данные: 
- в первой строке находятся числа E и F (\(1<=E<=F<=10000\));
- во второй - число N (\(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 33088. Гирьки
Темы: Задача о рюкзаке   

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

 

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

ID 33104. Сдача - 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 38366. Снова ка-штаны
Темы: Задача о рюкзаке   

В этой задаче, как и в задаче B, Петя снова собирает своего M-лапого Зверя на прогулку (однако количество лап у Зверя в этой задаче может быть до 1000). Снова ему мама оставила N штанов, имеющих соответственно K1, K2, …, KN штанин. Однако тетерь Петя хочет надеть на Зверя штаны так, чтобы выполнялись следующие условия:

  • на каждой лапе была надета хотя бы одна штанина (гарантируется, что это всегда возможно),
  • количество штанин, надетых на самую «утепленную» лапу, должно как можно меньше отличаться от количества штанин, надетых на самую легко одетую лапу (когда количество штанов, одетых на разные лапы, сильно отличается, Зверь испытывает дискомфорт),
  • в отличие от задачи B Петя не обязан надеть на Зверя все имеющиеся штаны — какие-то из них можно оставить дома.
Как и раньше, любые штаны можно надевать на любой набор лап. В частности, нельзя несколько штанин одних и тех же штанов надеть на одну и ту же лапу Зверя.

Помогите Пете – напишите программу, которая для каждой лапы укажет, сколько штанин должно быть на нее надето.

Входные данные
Вводится сначала число M, а затем число N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ Ki ≤ M). Сумма всех Ki не меньше, чем M.

Выходные данные
Выведите M строк, в i-ой строке должно быть выведено количество штанин, надетых на i-ю лапу. Если искомых ответов несколько, то выведите любой из них.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 4 3
1 2 3		 1
1
1
1		 Первые штаны надеты на лапу 1;
вторые штаны не используем;
третьи штаны надеты на лапы 2, 3 и 4.
Таким образом, на всех лапах по 1 штанине.
2 4 2
3 2		 2
1
1
1		 Первые штаны надеты на лапы 1, 2 и 3;
вторые штаны надеты на лапы 1 и 4.
Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2, а на остальных лапах по одной штанине, т.е. количество штанин на разных лапах отличается на один. Нетрудно заметить, что в этом примере нельзя одеть зверя так, чтобы на всех лапах было поровну штанин, поэтому этот ответ является оптимальным.