贪婪算法的汽车加油问题(使列表索引超出范围)

Question

我在使用贪婪算法解决汽车加油问题时遇到了一个小问题。

问题简介

您将前往距离家乡数英里的另一个城市。你的车可以行驶加满油最多跑几英里，然后从加满油开始。沿途有加油站，距离1站、2站、，stopN从您的家乡出发。需要的最低续杯次数是多少？

输入：

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循环和if语句时，如中所示

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

它正在进入一个无限循环。

你能指出我面临的错误吗？

Answer 1

几个问题：

• &不是布尔值和运算符。使用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

这可能会修复索引错误。您的代码的逻辑是正确的，这与我在else语句块中的代码中所做的相同。添加起点和终点(总距离)可以避免索引错误。首先检查总距离，看看它是否能装满油箱到达。如果没有，请执行else语句。

def compute_min_refills(distance, tank, stops):
numrefill, currentrefill= 0,0
stops = [0] + stops + [distance] #include the start and end points in the stops list   
if distance <= tank:
return 0
else:
while currentrefill < len(stops)-1:
lastrefill = currentrefill
#print(currentrefill, lastrefill, len(stops))
while currentrefill < len(stops)-1 and stops[currentrefill+1] - stops[lastrefill]<=tank:

currentrefill += 1
if currentrefill == lastrefill:
return -1
if currentrefill < len(stops)-1:
numrefill +=1
#print(numrefill)
return numrefill
if __name__ == '__main__':

#print(compute_min_refills(10, 3, [1,2,5,9]))

Answer 3

def car_refill(dist,cap,n,stops):
stops.insert(0,0)
stops.append(dist)
num_refill,curr_refill = 0,0
while curr_refill <= n:
last_refill = curr_refill
while (curr_refill <= n and stops[curr_refill + 1] - stops[last_refill] <= cap):
curr_refill += 1
if curr_refill == num_refill :
return -1
if curr_refill <= n:
num_refill +=1
return num_refill

试试这个。。。。

Answer 4

我不知道为什么，但答案似乎过于复杂，我只是想象自己开车，想出了这个简单的解决方案

function minfill(distance, miles, n, stations) {
//added final distance to last station for simplicity can simply push to array. 
stations = [...stations, distance]
let refill = 0,
limit = miles,
dt = 0, //distance travelled
current = 0; //current station
while (current <= n) {
//check if next  or first station is unreachable
if ((Math.abs(stations[current] - stations[current + 1]) > limit) || stations[0] > limit) return -1
//check if we need to refuel or pass
if (Math.abs(dt - stations[current]) <= limit) { 
current++
}
//if next distance was over limit we set distance tavelled to previous station ,current station was already pointed to next in above block
else {
dt = stations[current - 1]
refill++
}
}
return refill
}

p.s-这段代码是用node/javascript编写的，尽管我已经通过了这个问题的所有测试，但我知道这里有一些更聪明的人会帮助改进/纠正这段代码或提供一些指针。

Answer 5

导入java.util.；导入java.io.；

公共车厢加油

static int compute_refills(int dist, int tank, int stops[], int n) {
int current_refills=0;
int num_refills=0;
int last_refill=0;
while(current_refills<=n) {
last_refill = current_refills;
while ((current_refills !=stops.length-1) && (stops[current_refills + 1] - stops[last_refill]) <= tank) {
current_refills +=1 ;
}
if (current_refills == last_refill)
return -1;
if (current_refills <= n)
num_refills +=1;

}
return num_refills;
}

public static void main (String[]args){
Scanner scanner = new Scanner(System.in);
int dist = scanner.nextInt();
int tank = scanner.nextInt();
int n = scanner.nextInt();
int stops[] = new int[n * n * n];// to solve array index out of bound exception increase the size of the array
for (int i = 0; i < n; i++) {
stops[i] = scanner.nextInt();
}
System.out.println(compute_refills(dist, tank, stops, n));
}
}

Answer 6

将[0]和[d]添加到stop的答案应该有效，但current_refill比较应该处处为current_refill < len(stops)- 2，因为添加了两个stop。还有另一种方法可以解决这个问题。

def compute_min_number_of_refills(d, m, stops):
if d <= m:
return 0
total_refill = 0
last_refill = -1
limit = m 
stops.append(d)
i = 0
while i < len(stops):
if stops[i] >= limit: 
current_refill = i - 1 if stops[i] > limit else i
if current_refill == last_refill:
return -1 
last_refill = current_refill
total_refill += 1
limit = m + stops[current_refill]
i = current_refill + 1
else:
i += 1
return total_refill

Answer 7

我使用了这段代码，并从Coursera的一门课程中得到了正确的答案。

# python3
import sys
def compute_min_refills(distance, tank, stops):
capacity_tank = tank
refill = 0
if capacity_tank >= distance:
return 0
if capacity_tank < stops[0] or (distance-stops[-1]) > capacity_tank:
return -1
for i in range(1, len(stops)):
if (stops[i]-stops[i-1]) > capacity_tank:
return -1
if stops[i] > tank:
tank = (stops[i-1] + capacity_tank)
refill += 1
if distance > tank:
refill += 1
return refill

if __name__ == '__main__':
d, m, _, *stops = map(int, sys.stdin.read().split())
print(compute_min_refills(d, m, stops))

Answer 8

逻辑

这个想法是循环通过停车，检查每次停车是否小于汽车在一个装满油箱的情况下可以行驶的距离。如果是，则在前一站继续加油，并将该站作为新的起点重复此过程。

代码

def min_refills(distance, tank, stops):
stop_list = []
stops.append(distance) # append the destination to the stop list
# write your code here
if distance <= tank: # if the travel distance <= distance travelled in one full tank
return 0
else:
start = 0
prev = 0
for stop in stops:

if stop - start < tank:     # if refueling stop is closer to the starting point than the car can travel in one full tank
prev = stop     # move prev pointer to the refueling stop
elif (stop - start == tank) and (stop != distance):     # don't consider destination as a refueling stop
start = stop    # move the starting point to the current gas stop
stop_list.append(stop)      # add the refueling stop to the stop list
prev = stop     # move the prev pointer to the stop
elif stop - start > tank:
start = prev    # move the starting point to the prev gas stop
if stop - start > tank:     # if next refuleing stop is farther than the dist. car can go in one full tank
return -1
stop_list.append(prev)      # add the refueling stop to the list
prev = stop     # move the prev pointer the stop
return len(stop_list)

Answer 9

它处于无限循环中，因为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