Алгоритм динамического программирования для грузовика на дороге и проблема остановки топлива - PullRequest
Новая
       72

Алгоритм динамического программирования для грузовика на дороге и проблема остановки топлива

1 голос
/ 20 сентября 2019

Грузовик сжигает 1 единицу топлива при проезде 1 единицу расстояния.Грузовик должен доехать до города, который расположен на L единицах расстояния вдоль дороги, а в начальной точке грузовик имеет P единиц топлива в баке (оба значения дано как (L, P) пара).Топливный бак бесконечен, поэтому грузовик всегда может хранить больше топлива.Число возможных остановок подачи топлива вдоль дороги дается в виде пар целых чисел (a, b) , где a равно расстоянию между городом и заправкой , b - количество единиц топлива, которое может обеспечить эта остановка.

Цель состоит в том, чтобы сделать как можно меньше остановок на пути к городу.Алгоритм должен возвращать наименьшее количество остановок, необходимых для выполнения поездки.

Я выяснил, как решить эту проблему с помощью жадного алгоритма, используя очередь приоритетов, но я изо всех сил пытаюсь найти динамический подход кпроблема.Я знаю, что есть, но я не могу понять это.Буду признателен за любые подсказки.

1 Ответ

1 голос
/ 20 сентября 2019

Идея скопирована с https://leetcode.com/problems/minimum-number-of-refueling-stops/solution/,

Давайте определим dp [i], самое дальнее местоположение, которое мы можем получить, используя i i stop stop.Это связано с тем, что нам нужен самый маленький i, для которого dp [i]> = target.

Алгоритм

Давайте обновим dp, рассматривая каждую станцию ​​по порядку.Без станций ясно, что мы можем получить максимальное расстояние startFuel с 0 остановками заправки.

Теперь давайте посмотрим на шаг обновления.При добавлении станции станции [i] = (местоположение, пропускная способность), в любой момент, когда мы можем достичь этой станции с t остановками заправки, теперь мы можем достигнуть пропускной способности дальше с t + 1 остановками заправки.

Например, еслимы могли достичь расстояния 15 с 1 остановкой заправки, и теперь мы добавили станцию ​​в месте 10 с 30 литрами топлива, а затем потенциально могли бы достичь расстояния 45 с 2 остановками заправки. 

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    int N = stations.length;
    long[] dp = new long[N + 1];
    dp[0] = startFuel;
    for (int i = 0; i < N; ++i)
        for (int t = i; t >= 0; --t)
            if (dp[t] >= stations[i][0])
                dp[t+1] = Math.max(dp[t+1], dp[t] + (long) stations[i][1]);

    for (int i = 0; i <= N; ++i)
        if (dp[i] >= target) return i;
    return -1;
}

Анализ сложности

Сложность времени : O (N ^ 2) , где N - длина станций.

Сложность пространства : O (N) , пространство, используемое дп.

...