Проблема заправки автомобиля по жадному алгоритму (вывод списка из диапазона)

Question

У меня небольшая проблема с решением проблемы заправки автомобиля с использованием алгоритма Жадности.

Введение задачи

Вы собираетесь поехать в другой город, который расположен в ? милях от вашего родного города. Ваша машина может проехать не более ? миль на полном баке, и вы начинаете с полным баком. На вашем пути есть автозаправочные станции на расстоянии stop1 stop2. , , Остановись из твоего родного города. Какое минимальное количество пополнений необходимо?

Входные данные:

950
400
4
200 375 550 750

Выходные данные:

2

Что я пробовал с сейчас

def car_fueling(dist,miles,n,gas_stations):
  num_refill, curr_refill, last_refill = 0,0,0
  while curr_refill <= n:
    last_refill = curr_refill
    while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
        curr_refill += 1
    if curr_refill == last_refill:  
      return -1
    if curr_refill <= n:
      num_refill += 1
  return num_refill

В чем проблема, с которой я сталкиваюсь

В заявлении

while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles)

Я получаю ошибку IndexError: list index out of range. Это из-за gas_stations[curr_refill + 1]. Поэтому, когда я пытаюсь разделить его как while l oop и оператор if, как в

while (curr_refill <= n-1):
    if (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
        curr_refill += 1
    else:
        break

, он входит в бесконечное l oop.

Не могли бы вы указать на ошибку, с которой я столкнулся?

Заранее спасибо.

Answer 1

Несколько вопросов:

• & не является логическим оператором and-operator. Использование and
• curr_refill + 1 может быть n, и, следовательно, выдает ошибку, которую вы получили. Обратите внимание, что расстояние после последней АЗС можно определить с помощью dist
• . Значение last_refill неверно с самого начала: вы еще не заправили (пока) на станции 0 , поэтому он не должен быть инициализирован как 0. Вместо этого используйте другую переменную, которая показывает, как далеко вы можете в данный момент проехать.

Исправленный код:

def car_fueling(dist,miles,n,gas_stations):
    num_refill, curr_refill, limit = 0,0,miles
    while limit < dist:  # While the destination cannot be reached with current fuel
        if curr_refill >= n or gas_stations[curr_refill] > limit:
            # Cannot reach the destination nor the next gas station
            return -1
        # Find the furthest gas station we can reach
        while curr_refill < n-1 and gas_stations[curr_refill+1] <= limit:
            curr_refill += 1
        num_refill += 1  # Stop to tank
        limit = gas_stations[curr_refill] + miles  # Fill up the tank 
        curr_refill += 1
    return num_refill

# Test cases
print(car_fueling(950, 400, 4, [200, 375, 550, 750]))  # 2
print(car_fueling(10, 3, 4, [1, 2, 5, 9]))  # -1

Answer 2

Это бесконечно l oop, потому что n не увеличивается.

Увеличивайте n там, где это имеет смысл (например, в конце вашего оператора while).

def car_fueling(dist,miles,n,gas_stations):
    num_refill, curr_refill, last_refill = 0,0,0

    while curr_refill <= n:
        last_refill = curr_refill

        while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
            curr_refill += 1
        if curr_refill == last_refill:  
            return -1
        if curr_refill <= n:
            num_refill += 1

        n+=1 # Increment

  return num_refill