|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
26.06.2015, 23:17 | #1 |
Пользователь
Регистрация: 03.03.2013
Сообщений: 70
|
Новогодние подарки.Жадный алгоритм.
Добрый вечер.
Люди помогите понять, как тут применить жадность. Все что в голову пришло не подходить весь день думал.Только знаю что должно получиться максимальное пересечение между временем отправки и упаковкой другого подарка,та последовательность будет и оптимальней.но как это использовать не знаю..думал все что можно .Сортировать по максимальным пересечением не вариант..просто увеличению времени приготовления подарка не робит. Просто подскажите отсталому что тут применять ,буду счастлив Деду Морозу и Снегурочке нужно доставить n подарков детям. Зная время t1 упаковки каждого подарка Снегурочкой и время его доставки Дедом Морозом t2, вычислить наименьшее время, необходимое для выполнения всех заказов. В свой мешок Дед Мороз может положить только один подарок. Входные данные В первой строке находится количество подарков n (1 ≤ n ≤ 300). В следующих двух строках содержится по n чисел, соответственно: во второй строке – время упаковки каждого подарка Снегурочкой, а в третьей – время его доставки Дедом Морозом. Известно, что 0 < t1, t2 ≤ 1000. Выходные данные Наименьшее время доставки всех подарков. Входные данные 5 4 4 30 6 2 5 1 4 30 3 Выходные данные 47 |
27.06.2015, 11:30 | #2 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Называется это чудо - алгоритм Джонсона
Вечером скину свой вариант |
28.06.2015, 12:15 | #3 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Код:
|
02.07.2015, 16:51 | #4 |
Пользователь
Регистрация: 03.03.2013
Сообщений: 70
|
Спасибо!)Очень помог
Конечно я не понял откуда он смотрит на компоратор...и делает доводы по поводу если А - то раньше.если Б то позже. А так, смотря на компоратор явно видем что добиваемся максимального пересечение - что радует Код:
|
03.07.2015, 22:54 | #5 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Жадный алгоритм на графе | slimper86 | Помощь студентам | 4 | 27.06.2013 09:31 |
Разыгрываем и дарим Новогодние подарки от форума :) | Alar | Свободное общение | 42 | 31.12.2012 17:16 |
Жадный алгоритм? | Loki_veil | Помощь студентам | 0 | 27.06.2012 12:05 |
Жадный алгоритм | merhaba1992 | Помощь студентам | 1 | 05.11.2011 00:24 |
Жадный алгоритм в программировании | nikita92 | Помощь студентам | 0 | 26.11.2010 20:20 |