минимальная остановка, чтобы добраться до места назначения - PullRequest
Новая
       27

минимальная остановка, чтобы добраться до места назначения

0 голосов
/ 24 мая 2018 
Class GasStation {
    int distanceToDestination;
    int availableGas;
}

с учетом трех параметровd g представляет начальное количество газа в транспортном средстве, d представляет расстояние до пункта назначения.и список gasStation, где для каждой gasStation переменная равна distanceToDestination , и доступна вторая секундаГаз этой станции.Как рассчитать минимальную остановку, чтобы добраться до места назначения? 

g = 10 gallon,
d = 20 miles,
list of GasStation:
gasStations = [[15, 1], [14,10], [12,12]].

Редактировать: ограничения по пропускной способности нет.

1 Ответ

0 голосов
/ 24 мая 2018

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

gasStations  = [list of GasStations]
sort gasStations  by decreasing value of distanceToDestination if its not already sorted
k : gas required to travel 1 mile
maxNumberOfGasStation : maximum gas stations possible
maxPossibleCapacity : maximum gas that might be required for a trip
memo = [maxNumberOfGasStation][maxPossibleCapacity] filled up with -1

int f(idx, currentGas) {
    if (G[idx].distanceToDestination * k <= current_gas) {
        // You can reach destination using the gas you have left without filling any more
        return 0
    }
    if(idx == gasStations.length - 1) {
        // last station
        if (G[idx].distanceToDestination * k > current_gas + G[idx].availableGas) {
            // You cannot reach destination even if you fill up here
            return INT_MAX
        } else{
            return 1;
        }
    }   
    if(memo[idx][currentGas] != -1) return memo[idx][currentGas];

    // option 1: stop at this station
    int distBetweenStation = G[idx].distanceToDestination - G[idx+1].distanceToDestination
    int r1 = 1 + f(idx+1, min(currentGas + G[idx].availableGas, maxPossibleCapacity) - distBetweenStation * k)

    // option 2: don't stop at this station
    int r2 = f(idx+1, currentGas - distBetweenStation * k)

    // take minimum
    int r = min(r1, r2)

    memo[idx][currentGas] = r
    return r;
}

Чтобы получить ответ на звонок f(0, g - (d - gasStations[0].distanceToDestination) * k).Сложность времени составляет O(maxNumberOfGasStation * maxPossibleCapacity).Если есть предел capicity, вы можете просто заменить его maxPossibleCapacity.

...