Российский экономический

Объемы, веса и количество предметов в каждой группе 
1 
2 
3 
4 
5 
Вес, кг 
3 
4 
5 
8 
9 
Цена, тыс. руб. 
1 
6 
6 
7 
6 
180

---

Максимизируйте общий вес рюкзака,
чтобы суммарная стоимость была 
бы максимальной. Для каждой вещи вычислите коэффициент отношения цены 
к его весу, затем возьмите те вещи, у которых этот коэффициент максимален и 
которые помещаются в рюкзак. 
4.
 
В рюкзак объема 7 единиц необходимо положить пять предметов. Объ-
емы, веса и количество предметов в каждой группе приведены в таблице. 
Таблица 
Объемы, веса и количество предметов в каждой группе 
Объем, единицы 
1 
2 
3 
1 
1 
Вес, кг 
2 
3 
2 
4 
1 
Количество 
1 
3 
3 
1 
2 
Максимизируйте общий вес рюкзака
. 
5. 
В рюкзак необходимо положить предметы, вес, количество и стоимость 
каждого 
составляют соответственно: 1, 2, 2; 3, 4, 2; 5, 6, 3; 4, 7, 4; 3, 3, 5; 2, 1, 3.
Определите, какие предметы следует положить в рюкзак, чтобы их вес не пре-
вышал 50 кг, а стоимость набора была бы максимальной. 
6. Дано восемь предметов, каждый из них имеет массу соответственно 2, 
3, 4, 5, 6, 7, 8, 9 кг и стоимостью соответственно 2, 3, 4, 5, 6, 7, 8, 9 тыс. руб. 
Необходимо сформировать из этих предметов такой набор, чтобы суммарная 
масса не превосходила веса 70 кг грузоподъемности рюкзака, а суммарная сто-
имость была бы максимальной.
7. Путешественник собрался в поход. Перед ним перечень из пяти необ-
ходимых предметов, для каждого известна стоимость (4, 1, 8, 7, 1) и определен 
вес (6, 5, 3, 1, 7). Имеется рюкзак грузоподъемностью 35. Требуется упаковать 
рюкзак так, чтобы общая ценность упакованных предметов была наибольшей, а 
их общий вес не превосходил грузоподъемности рюкзака. 
8.
 
Три станка обрабатывают детали с одинаковой скоростью. Известны 
длительности обработки 
n
деталей; порядок обработки не важен. Обработка де-
талей не прерывается — станок переключается на обработку следующей детали 
мгновенно. Необходимо так распределить детали между станками, чтобы обра-
ботка последней из них закончилась как можно скорее. По этому алгоритму де-
тали с длительностью обработки 12, 8, 7, 5, 4 распределяются по станкам так: 
12, 8 + 4, 7 + 5. Очевидно, лучше быть не может. Однако если длительности 12, 
8, 7, 5, 4, 2, то жадный алгоритм даст распределение 12 + 2, 8 + 4, 7 + 5 с мо-
ментом окончания 14, хотя распределение 12, 8 + 5, 7 + 4 + 2 имеет момент 
окончания 13. 
9.
 
Путешественник задумал повторить путь А.Н. Радищева «из Петербур-
га в Москву», для чего решил воспользоваться личным автомобилем и решил 
так спланировать свой маршрут, чтобы минимизировать затраты. Для этого ему 
нужно было знать, сколько на его пути встретится заправочных станций и на 
каком расстоянии друг от друга они находятся. Помимо всего прочего, прихо-
дилось учитывать, что емкость бензобака машины ограничена. Требуется опре-
делить, какое минимальное количество заправок ему нужно посетить. Первая 
АЗС находится в Петербурге, а последняя — в Москве. 
Di — 
расстояние от 
i
-й 
181

---

до (
i
+ 1)-й заправки; 
S
— расстояние, которое машина может проехать с пол-
ным баком; 
L
— расстояние от Петербурга до Москвы. В решении задачи нуж-
но получить номера заправок, на которых придется заправляться. Путеше-
ственник заправляет полный бак в исходной точке маршрута — Петербурге. 
Если от данной заправки до Москвы бензина достаточно, то едем в Москву; 
иначе находим самую удаленную заправку, до которой можно доехать, и едем 
туда, заправляем полные баки и повторяем шаг 2. 
10.
 
Перед праздниками шеф получает очень много приглашений на тор-
жественные заседания. Чтобы лучше планировать свое время, шеф ввел прави-
ло, чтобы в каждом из приглашений четко указывался отрезок времени заседа-
ний. Шеф не любит половинчатых решений, поэтому или находится на заседа-
нии все указанное время, или не приходит на него. Между посещениями засе-
даний должен быть хотя бы минимальный перерыв, т.е. шеф может успеть на 
j
-
е заседание по списку приглашений. Напишите план, позволяющий шефу посе-
тить как можно больше заседаний. 
В этой задаче правильным оказывается неожиданно простой жадный ал-
горитм: на первом шаге выбрать заседание с наименьшим значением 
b
, на каж-
дом следующем шаге — с наименьшим значением 
b
, но только среди тех засе-
даний, которые начинаются после конца предыдущего выбранного. Для реали-
зации представленного алгоритма сначала отсортируем массив интервалов вре-
мени по неубыванию значений 
b
. Поскольку для окончательного ответа нужны 
исходные номера заседаний, целесообразно организовать данные в записи с по-
лями 
a
, 
b
, 
idx
(границы интервала заседания и его номер в начальном списке) и 
сортировать записи по значениям в поле 
b
. 
11. Монетный двор выпускает монеты номиналом 25, 10, 5, 2, 1 коп. Раз-
работайте алгоритм-программу, которая позволяла бы сумму в 
N
коп. разме-
нять данными монетами, используя жадный алгоритм. 
12. 
Математически задачу можно сформулировать так: имеется 
n
грузов, 
и для каждого груза определены вес 
Р
и ценность 
С
, известна грузоподъем-
ность контейнера 
W
. Необходимо выбрать подмножество грузов так, чтобы их 
общий вес не превышал 
W
, а суммарная их ценность была бы максимальной.
13. По 
жадному алгоритму
 предметы сортируются по убыванию стоимо-
сти единицы веса каждого. В рюкзак последовательно складываются самые до-
рогие за единицу веса предметы из тех, что помещаются внутри. Сложность 
сортировки предметов 
О
(
N
log(
N
)) . Далее происходит перебор всех 
N
элемен-
тов. Точное решение можно получить не всегда. Пусть вместимость рюкзака 
P
= 80. Предметы уже отсортированы. Примените жадный алгоритм. 
Таблица