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

Есть вот такая вот задача . На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое задается одним целым числом — расстояни*ем в метрах от начальной отметки. Все монеты расположены правее начальной отметки. Али-баба бегает по дороге и собирает монеты, начиная делать это в момент времени 0. За одну секунду он пробегает ровно один метр. У каждой монеты есть крайний срок, до которого (включительно) ее нужно подобрать, иначе монета исчезнет. Али-баба должен собрать все монеты и сделать это за минимально возможное время. Он может старто*вать в любой точке прямой, собирать монеты в произвольном порядке, но обязательно нужно успеть собрать все монеты и при этом минимизировать затраченное время.
Задается число n — количество монет , для каждой монеты задается по 2 целых числа, первое из которых задает положение монеты, а второе — крайний срок в секундах, за который нужно успеть собрать эту монету. Нужно найти минимальное время сбора всех монет или сказать , что собрать все монеты невозможно.
Собственно , меня интересует только алгоритм решения (очень похоже на динамическое программирование , но как я не пробовал , не получается) и какие структуры данных лучше использовать . Буду благодарен за любую помощь .

0

Если я правильно понял условие, то графически данную задачу можно представить как одномерную полуось, т.е. например только положительное направление оси X.
Начало координат расположено в начальной точке с координатой 0.
На этой оси имеется n точек (монет). Их координаты даны по условию.
Как я понимаю Али-баба может передвигаться от точки к точке и при этом сам выбирать первую точку.

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

int coord; // Координата (дана по условию)
int time; // Срочность/время на сбор (также дано)
bool take; // Показатель того, что монета собрана (точка посещена)

0

De_N, надо найти минимальное время. К примеруВаш алгоритм выведет 3, а минимальное время 2.

0

Сообщение от De_N Мне кажется нужно начинать от самой срочной точки (монеты) и двигаться по мере уменьшения срочности. Находясь в текущей точке, вибирать самую срочную и вычислять до нее расстояние.

Не все так просто. Допустим очередные по срочности оказались две монеты, причем можно успеть собрать одну а потом другую в любом порядке. Вот здесь может очень важным оказаться порядок их сбора, вернее где мы закончим сбор: около первой или второй (следующую по срочности монету после этих двух монет, можно успеть собрать из какого-то одного положения).
Или вот вариант:
Али-баба находится в точке 10, текущее время 10.
Остались две монеты: 3 19 и 11 20. Если двинуться за более срочной (которая на расстоянии 3), то вторую не успеем забрать. Здесь правильнее будет взять сначало на расстоянии 11, а затем на расстоянии 3.
Здесь, по-моему, лучше воспользоваться графами (поиском в глубину).

0

Ок. Справедливо

Добавлено через 3 часа 27 минут
Подумал, подумал..
Мне кажется при таких условиях единственным выходом будет перебор решений. Должно быть некоторая часть решений отсеится уже на первых "ходах".
Ведь программа в праве сама выбирать первую монету. То есть если представлять решение как граф, его начальная точка (первая монета) не определена заранее.
К сожалению я не очень силен в теории графов, поэтому делаю лишь предположение.

0

Вот-вот , вообще непонятно с какой монеты надо начинать , а перебором не годится (

0

Нужно использовать динамическое программирование

Пусть будет 10 монет.
Во-первых, заметим что последний прыжок Алибабы приходится либо на первую, либо на последнюю монету.
Во-вторых, рассмотрим когда прыжок на первую (аналогично для последней). С какой монеты он может прыгнуть на нее? Со второй либо с последней.
В-третьих, оптимальное решение для 10 монет - это оптимальное решение для первых 9 + прыжок, либо для последних 9 + прыжок. Итого 4 случая.

0