The Truck Refueling Problem

A truck company runs its business
on a fixed route from city A to city B. There are n+1 stops s_{0}, s_{1},
s_{2}, …, s_{n} on this fixed route,
and the route starts from the stop s_{0} in city A with a full tank of
gas and ends in stop s_{n} in city B. All the
intermediate stops s_{1}, s_{2}, …, s_{n-1}
can provide gas. Since this is a long trip, the truck need to refuel somehow in
some of these intermediate stops s_{1}, s_{2},
…, s_{n-1}. **Let P _{i }be
the price of gas per at stops s_{i}**.

1. **Let’s try to minimize the number of refueling
stops.** (i) Devise a polynomial-time algorithm (if
possible) to determine in which intermediate stops the truck should get
refueled to full tank to **minimize the
total number of stops for refueling along the route**. (ii) What is the
complexity of your algorithm? (iii) Can you prove that your algorithm does
always find a solution that minimizes the total number of stops for refueling along
the route?

2. **Let’s try to minimize the total refueling
cost**. (i) Devise a polynomial-time algorithm (if
possible) to determine in which intermediate stops the truck should get
refueled and the numbers of gallons refueled respectively (in other words, you
don’t have to fill the tank entirely every time) to minimize the total amount
of refueling cost on the route. (ii) What is the complexity of your algorithm?
(iii) Can you prove that your algorithm does always find a solution that
minimizes the total amount of refueling cost?

Examples:

1. Samples: Case 1 and Case 2 (solved)

2. Test case: What is the optimal solution you get?