Эксперт

Сергей

Задать вопрос

Мы готовы помочь Вам.

Цель работы: Ознакомиться с методами решения задач, используя жадные алгоритмы.
Порядок выполнения работы
1. Ознакомиться с теоретическими сведениями.
2. Получить вариант задания у преподавателя.
3. Выполнить задание: написать программу на языке С++.
4. Продемонстрировать выполнение работы преподавателю.
5. Оформить отчет.
6. Защитить лабораторную работу.
Требования к оформлению отчета
Отчет по лабораторной работе должен содержать следующие разделы:
титульный лист; цель работы; задание на лабораторную работу; ход работы;
ответы на контрольные вопросы; выводы по проделанной работе.
Варианты заданий
1. Написать программу для решения задачи, используя жадные алгоритмы. Толик придумал новую технологию программирования. Он хочет уговорить друзей использовать ее. Однако все не так просто. i-й друг согласится использовать технологию Толика, если его авторитет будет не меньше ai (авторитет выражается целым числом). Как только i-й друг начнет ее использовать, к авторитету Толика прибавится число bi (попадаются люди, у которых bi < 0). Помогите Толику наставить на путь истинный как можно больше своих друзей. Входные данные: на первой строке содержатся два целых числа: Количество друзей у Толика n и первоначальный авторитет Толика a0 (−109≤a0≤109). Следующие n строк содержат пары целых чисел ai и bi (−109≤ ai , bi ≤109). Выходные данные: на первой строке выведите число m − максимальное число друзей, которых может увлечь Толик. На второй строке выведите m чисел − номера друзей в том порядке, в котором их нужно агитировать.
2. Написать программу для решения задачи, используя жадные алгоритмы. Мальчик Костя очень любит конфеты, но мама не разрешает ему брать их слишком много. Поэтому каждый раз, когда Костя хочет съесть конфету, мама предлагает ему сыграть в игру. Изначально у Кости нет конфет, а у мамы их N (они пронумерованы от 1 до N). На каждой конфете мама написала два числа Ai и Ci. Мама очень следит за уровнем вредности конфет, который получает ее сын. Изначально этот уровень равен 0. На каждом ходу игры Костя может взять одну конфету. Если Костя возьмет конфету с номером i, то уровень вредности увеличивается на Ai. Если сразу после этого уровень вредности становится большей Ci, то брать эту конфету запрещается. Брать конфеты можно в произвольном порядке, но одну и ту же можно брать не более одного раза. Помогите Косте взять как можно больше конфет (вне зависимости от финального уровня вредности). Входные данные: в первой сроке входных данных записано целое число N (1≤N≤1000) − количество видов конфет. Во второй строке записаны N целых чисел Ai (1≤Ai≤106). В третей строке записаны N целых чисел Ci (1≤Ci≤109). Выходные данные: в единственной
строке выведите целое число, равное максимальному количеству конфет, которые может взять Костя.
3. Написать программу для решения задачи, используя жадные алгоритмы. Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Тулы. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме. Глубина ямы равна H. Каждый школьник знает свой рост по плечи hi и длину своих рук li. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте hi+li от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j1
j2
jk, то он может дотянуться до уровня hj1+hj2+
+hjk+hi+li. Если школьник может дотянуться до края ямы (то есть hj1+hj2+
+hjk+hi+li ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся. Найдите наибольшее количество школьников, которые смогут выбраться из ямы до прибытия помощи, и перечислите их номера. Входные данные: В первой строке записано натуральное число N — количество школьников, попавших в яму. Далее в N строках указаны по два целых числа: рост i-го школьника по плечи hi и длина его рук li. В последней строке указано целое число — глубина ямы H. Выходные данные: В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K>0, то во второй строке выведите их номера в том порядке, в котором они вылезают из ямы. Школьники нумеруются с единицы в том порядке, в котором они заданы во входном файле. Если существует несколько решений, выведите любое.
4. Написать программу для решения задачи, используя жадные алгоритмы. У Васи в комнате очень много коробок, которые валяются в разных местах. Васина мама хочет, чтобы он прибрался. Свободного места в комнате мало и поэтому Вася решил собрать все коробки и составить их одну на другую. К сожалению, это может быть невозможно. Например, если на картонную коробку с елочными украшениями положить что-то железное и тяжелое, то вероятно следующий Новый год придется встречать с новыми игрушками. Вася взвесил каждую коробку и оценил максимальный вес который она может выдержать. Помогите ему определить какое наибольшее количество коробок m он сможет составить одну на другую так, чтобы для каждой коробки было верно, что суммарный вес коробок сверху не превышает максимальный вес, который она может выдержать. Входные данные: первая строка содержит целое число n (1≤n≤105) — количество коробок в комнате. Каждая следующая из n строк содержит два целых числа wi и ci (1≤wi≤105,1≤ci≤109), где wi − это вес коробки с номером i, а ci − это вес который она может выдержать. Выходные данные:
одно число − ответ на задачу.
5. Написать программу для решения задачи, используя жадные алгоритмы. Дана лекционная аудитория, в которой несколько профессоров хотят прочесть свои лекции. Для составления расписания профессора подали заявки, вида [si, fi) – время начала и конца лекции. Лекция считается открытым полуинтервалом, то есть какая-то лекция может начаться в момент окончания другой, без перерыва. Составьте расписание занятий так, чтобы выполнить максимальное количество заявок. Входные данные: в первой строке вводится натуральное число N, не более 1000 – общее количество заявок. Затем вводится N строк с описаниями заявок — по два числа в каждом si и fi. Гарантируется, что si < fi. Время начала и окончания лекции – натуральное число, не превышает 1440 (в минутах с начала
суток). Выходные данные: выведите одно число – максимальное количество заявок, которые можно выполнить.
6. Написать программу для решения задачи, используя жадные алгоритмы. В некоей воинской части есть сапожник. Рабочий день сапожника длится N минут. Заведующий складом оценивает работу сапожника по количеству починенной обуви, независимо от того, насколько сложный ремонт требовался в каждом случае. Дано k сапог, нуждающихся в починке. Определите какое максимальное количество из них сапожник сможет починить за один рабочий день. Входные данные: в первой строке вводятся число N (натуральное, не превышает 1000), и число k (натуральное, не превышает 500). Затем идет k чисел – количество минут, которые требуются чтобы починить i-й сапог (времена – натуральные числа, не превосходят 100). Выходные данные: выведите единственное число – максимальное количество сапог, которые можно починить за один рабочий день.
7. Написать программу для решения задачи, используя жадные алгоритмы. Андрей едет из пункта A в пункт B на автомобиле. Расстояние между этими пунктами равно N километров. Известно, что с полным баком автомобиль способен проехать k километров. Дана карта, на которой отмечены координаты бензоколонок, относительно пункта A. Определите минимальное число заправок, которые придется сделать Андрею чтобы успешно достичь пункта B. Известно, что при выезде из пункта A бак был полон. Входные данные: в первой строке вводятся числа N и k (натуральные, не превосходят 1000). В следующей строке вводится количество бензоколонок S, потом следует S натуральных чисел, не превосходящих N – расстояния от пункта A до каждой заправки. Заправки упорядочены по удаленности от пункта A. Выходные данные: если при данных условиях пункта B достичь невозможно, то вывести число -1. Если решение существует, то вывести минимальное количество остановок на дозаправку, которое нужно чтобы достичь пункта B.
8. Написать программу для решения задачи, используя методами жадные алгоритмы. В некотором королевстве есть N провинций. Король пожелал объединить все их под своей самодержавной властью. Естественно, чтобы никто не догадался об этих планах, он будет это делать поэтапно, а именно: раз в год он будет объединять какие-то две провинции в одну. Чтобы жителям обеих провинций не было обидно, новому территориальному образованию будет присвоено новое название, которое будет отличаться от обоих старых названий. Естественно, это потребует выпуска новых паспортов для жителей обеих провинций. Очевидно, что если в первой провинции pi жителей, а во второй – pj жителей, то для них надо выпустить pi+pj новых паспортов. На следующий год король объединяет еще какие-то две провинции. И так далее, до тех пор пока вся территория королевства не будет объединена в одну большую «провинцию». Определите, какое наименьшее количество новых паспортов придется выпустить, если король будет объединять провинции оптимально с этой точки зрения. Входные данные: в первой строке вводится число N (натуральное, не превышает 105) – количество провинций. Затем вводится N чисел – количество жителей каждой провинции (натуральное, не превосходит 109). Гарантируется, что изначально в королевстве хотя бы две провинции. Выходные данные: выведите единственное число – количество новых паспортов, которые придется выпустить.
9. Написать программу для решения задачи, используя жадные алгоритмы. Толик придумал новую технологию программирования. Он хочет уговорить друзей использовать ее. Однако все не так просто. i-й друг согласится использовать технологию Толика, если его авторитет будет не меньше ai (авторитет
выражается целым числом). Как только i-й друг начнет ее использовать, к авторитету Толика прибавится число bi (попадаются люди, у которых bi < 0). Помогите Толику наставить на путь истинный как можно больше своих друзей. Входные данные: на первой строке содержатся два целых числа: Количество друзей у Толика n и первоначальный авторитет Толика a0 (−109≤a0≤109). Следующие n строк содержат пары целых чисел ai и bi (−109≤ ai , bi ≤109). Выходные данные: на первой строке выведите число m − максимальное число друзей, которых может увлечь Толик. На второй строке выведите m чисел − номера друзей в том порядке, в котором их нужно агитировать.
10. Написать программу для решения задачи, используя жадные алгоритмы. Мальчик Костя очень любит конфеты, но мама не разрешает ему брать их слишком много. Поэтому каждый раз, когда Костя хочет съесть конфету, мама предлагает ему сыграть в игру. Изначально у Кости нет конфет, а у мамы их N (они пронумерованы от 1 до N). На каждой конфете мама написала два числа Ai и Ci. Мама очень следит за уровнем вредности конфет, который получает ее сын. Изначально этот уровень равен 0. На каждом ходу игры Костя может взять одну конфету. Если Костя возьмет конфету с номером i, то уровень вредности увеличивается на Ai. Если сразу после этого уровень вредности становится большей Ci, то брать эту конфету запрещается. Брать конфеты можно в произвольном порядке, но одну и ту же можно брать не более одного раза. Помогите Косте взять как можно больше конфет (вне зависимости от финального уровня вредности). Входные данные: в первой сроке входных данных записано целое число N (1≤N≤1000) − количество видов конфет. Во второй строке записаны N целых чисел Ai (1≤Ai≤106). В третей строке записаны N целых чисел Ci (1≤Ci≤109). Выходные данные: в единственной строке выведите целое число, равное максимальному количеству конфет, которые может взять Костя.

Контрольные вопросы
1. Что такое жадные алгоритмы?
2. Какие классы задач можно решать с помощью жадных алгоритмов? Пример.