Форум программистов, компьютерный форум CyberForum.ru

Алгоритм решения задачи - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.76
dota
3 / 3 / 0
Регистрация: 20.09.2010
Сообщений: 100
21.10.2012, 14:15     Алгоритм решения задачи #1
Есть вот такая вот задача . На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое задается одним целым числом — расстояни*ем в метрах от начальной отметки. Все монеты расположены правее начальной отметки. Али-баба бегает по дороге и собирает монеты, начиная делать это в момент времени 0. За одну секунду он пробегает ровно один метр. У каждой монеты есть крайний срок, до которого (включительно) ее нужно подобрать, иначе монета исчезнет. Али-баба должен собрать все монеты и сделать это за минимально возможное время. Он может старто*вать в любой точке прямой, собирать монеты в произвольном порядке, но обязательно нужно успеть собрать все монеты и при этом минимизировать затраченное время.
Задается число n — количество монет , для каждой монеты задается по 2 целых числа, первое из которых задает положение монеты, а второе — крайний срок в секундах, за который нужно успеть собрать эту монету. Нужно найти минимальное время сбора всех монет или сказать , что собрать все монеты невозможно.
Собственно , меня интересует только алгоритм решения (очень похоже на динамическое программирование , но как я не пробовал , не получается) и какие структуры данных лучше использовать . Буду благодарен за любую помощь .
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
De_N
16 / 14 / 2
Регистрация: 15.10.2012
Сообщений: 33
21.10.2012, 16:02     Алгоритм решения задачи #2
Если я правильно понял условие, то графически данную задачу можно представить как одномерную полуось, т.е. например только положительное направление оси X.
Начало координат расположено в начальной точке с координатой 0.
На этой оси имеется n точек (монет). Их координаты даны по условию.
Как я понимаю Али-баба может передвигаться от точки к точке и при этом сам выбирать первую точку.

Лично моё мнение об алгоритме:
Мне кажется нужно начинать от самой срочной точки (монеты) и двигаться по мере уменьшения срочности.
Находясь в текущей точке, вибирать самую срочную и вычислять до нее расстояние. Если это расстояние (оно же и время, необходимое на путь) больше срочности, то монету нельзя собрать -> задача не решается.
Если же уложиться во время можно, то отмечаем текущую точку как посещенную (собрали монету) и переходим к следующей. Действия повторяются.
Если всё это верно, думаю будет удобно использовать для описания точки структуру с полями:

int coord; // Координата (дана по условию)
int time; // Срочность/время на сбор (также дано)
bool take; // Показатель того, что монета собрана (точка посещена)
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
21.10.2012, 16:17     Алгоритм решения задачи #3
De_N, надо найти минимальное время. К примеру
Код
3 - 2 - 5
Ваш алгоритм выведет 3, а минимальное время 2.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.10.2012, 16:19     Алгоритм решения задачи #4
Цитата Сообщение от De_N Посмотреть сообщение
Мне кажется нужно начинать от самой срочной точки (монеты) и двигаться по мере уменьшения срочности.
Находясь в текущей точке, вибирать самую срочную и вычислять до нее расстояние.
Не все так просто. Допустим очередные по срочности оказались две монеты, причем можно успеть собрать одну а потом другую в любом порядке. Вот здесь может очень важным оказаться порядок их сбора, вернее где мы закончим сбор: около первой или второй (следующую по срочности монету после этих двух монет, можно успеть собрать из какого-то одного положения).
Или вот вариант:
Али-баба находится в точке 10, текущее время 10.
Остались две монеты: 3 19 и 11 20. Если двинуться за более срочной (которая на расстоянии 3), то вторую не успеем забрать. Здесь правильнее будет взять сначало на расстоянии 11, а затем на расстоянии 3.
Здесь, по-моему, лучше воспользоваться графами (поиском в глубину).
De_N
16 / 14 / 2
Регистрация: 15.10.2012
Сообщений: 33
21.10.2012, 21:12     Алгоритм решения задачи #5
Ок. Справедливо

Добавлено через 3 часа 27 минут
Подумал, подумал..
Мне кажется при таких условиях единственным выходом будет перебор решений. Должно быть некоторая часть решений отсеится уже на первых "ходах".
Ведь программа в праве сама выбирать первую монету. То есть если представлять решение как граф, его начальная точка (первая монета) не определена заранее.
К сожалению я не очень силен в теории графов, поэтому делаю лишь предположение.
dota
3 / 3 / 0
Регистрация: 20.09.2010
Сообщений: 100
21.10.2012, 21:54  [ТС]     Алгоритм решения задачи #6
Вот-вот , вообще непонятно с какой монеты надо начинать , а перебором не годится (
Yandex
Объявления
21.10.2012, 21:54     Алгоритм решения задачи
Ответ Создать тему
Опции темы

Текущее время: 18:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru