[Python] How to minimize refueling stops and tax for visiting cities in a fixed order?

Question: I am working on a problem where a salesman has to visit n cities by car in a fixed order (i.e., the order of visits is imposed by the numbering: city c1 is the starting point, c2 the second city, and so on, until the last city cn). The distance between two cities ci and cj is represented as d(ci, cj).

The car has the following constraints:

It consumes 1 liter of gasoline per kilometer. It has a maximum fuel capacity of C liters. The distance between two consecutive cities is always less than or equal to C (i.e., d(ci, ci+1) ≤ C for i = 1 to n-1), so it’s possible to travel between consecutive cities without running out of fuel. The salesman starts with a full tank at city c1, and at each city ci, he can either:

Continue driving without refueling, or Stop and refuel the car to its maximum capacity. Additionally, the salesman must fully refuel when he reaches his final destination cn.

I have done this, it was an easy greedy + proof of optimality of greedy.

Now we add a Tax Rule:

Whenever the salesman decides to refuel at city ci, he has to pay a tax in euros equal to the square of the number of liters remaining in the tank at that city. This tax also applies at the final destination cn, where the salesman must refuel.

For example:

If the salesman arrives at city ci with 4 liters of gasoline remaining, and he decides to refuel, he will pay a tax of 16 euros.

I proved with a counter exemple that greedy wasn't optimal but i am struggling to find the recursive answer for dynamic programming

I have tried tons of things, here is one of my idea :

dp(i,C) = 0 if c = 0; else min(dp(i+1,c - d(i,i+1)) ; dp(i+1,C) + c^2) But i am not sure if it works

import copy

def solution_tst (cities,C):
full = C
stop = 0
tax = 0
for i in cities :
if C < i :
tax+= C**2
C = full
stop +=1
C = C - i

return stop + 1,tax +C**2




Thanks !

Continue reading...