Алгоритм, подобный бензоколонке, с минимальными затратами? Жадный или ДП?

У меня есть массив n автозаправочных станций D[] на шоссе, что D[i] является расстояние от станции i с начала шоссе.Алгоритм, подобный бензоколонке, с минимальными затратами? Жадный или ДП?

У меня также есть ряд издержек C[], так что C[i] - это стоимость моего автомобиля, обслуживаемого на станции i.

Мне нужно, чтобы мой автомобиль обслуживался на первой станции, а мой автомобиль может проехать не более 100 миль между станциями.

Каков наиболее эффективный алгоритм, который можно получить от начала шоссе до конца с наименьшими затратами (мне нужно знать, на каких станциях останавливаться)? Я был в состоянии найти жадное решение для минимизации количества остановок, но при минимальных затратах, я имею в вид DP, с оптимальной подзадачей:

bestcost[j] = min(0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100)

и имею отдельный массив last[j], содержащие последнюю станцию который останавливается, что было бы лучшим i сверху подзадачи.

Будет ли это правильным подходом или есть лучшее решение Greedy/DP?

источник

2014-01-27 Anagha

Я не вижу жадного решения. Повторение DP правильное. Вы можете получить runtime 'O (n)' с монотонной очередью, которая позволяет вам найти min в 'O (1)', что является оптимальным, а также имеет низкий постоянный коэффициент. Это даже работает, если диапазон вашего велосипеда не постоянный. –

@NiklasB. на самом деле его решение жадное, на каждой остановке он будет искать лучший вариант, используя только стоимость. Его решение отлично работает, за исключением того, что оно не оптимально, поскольку он не рассматривает, сколько газа существует на каждом расстоянии и сколько он может повторите заполнение этой ценой, сделайте проблему здесь более сложной и сделайте более дешевую цену за газ-блок не всегда лучшим вариантом для остановки –

@KhaledAKhunaifer, пожалуйста, внимательно прочитайте мой вопрос, я не думаю, насколько газ существует, потому что это не проблема бензоколонки, а вариация. Это проблема с сервисной станцией, когда мне приходится фиксировать расходы 'C [i]' каждый раз, когда я останавливаюсь на данной станции 'i'. – Anagha

Рецидив лучше записать в виде

bestcost_serviced_at[j] = 
    min(0<i<j: bestcost_serviced_at[i] + C[j] s.t. D[j]-D[i] <= 100)

, потому что повторение дает оптимальную стоимость при условии, что транспортное средство фактически останавливается на станции j для обслуживания.

Тогда решение задачи

min (j: bestcost_serviced_at[j] s.t. highway_end - D[j] <= 100)

Я не думаю, что жадный алгоритм будет работать.

источник

2014-01-27 10:13:04

Я думаю, что ваш DP является немного неполным, вот рецидив DP, который является более всесторонним: -

if(highway_end-D[i]>100) { 

    minCost[i] = min(0<i<j && D[j]-D[i] <= 100 : minCost[j]+C[i]) 
} 

else minCost[i] = C[i]  

minCost[i] = minimum cost to reach destination if you have filled up at i

Сортировать станции в соответствии с расстоянием от начала и использовать DP в верхней на нижнюю станции расстояния. Используйте отсортированный массив для поиска ближайших соседних станций < = 100 миль.

Edit: -

Может быть сделано в O(NlogN) с использованием мин кучи.

источник

2014-01-27 14:13:34

Может быть реализован в 'O (n)', хотя если расстояния предварительно отсортированы –

@NiklasB. даже если он предрешен, как удовлетворить D [j] -D [i] <= 100 и min (minCost [j]) в O (1) для каждой подзадачи? –

Дерево сегментов дает вам O (log n) для каждого перехода. Как я уже упоминал, монотонная очередь с алгоритмом скользящего окна даже допускает постоянные переходы времени. Я напишу ответ позже. –

Алгоритм, подобный бензоколонке, с минимальными затратами? Жадный или ДП?

ответ

Смежные вопросы