I am in need of help proving that an algorithm has greedy choice property and optimal substructure.
Context of the problem:
Consider a problem where a company owns $n$ gas stations that are connected by a highway. Each gas station has a limited supply $g_i$ of gas-cans. Since the company don't know which gas station is most visited they want all of them to have the same amount of gas.
So they hire a fueling-truck to haul gas between the stations in their truck. However, truck also consumes 1 gas-can per kilometer driven.
Your task will be to help the chain calculate the largest amount of gas-cans $\bar g$ they can have at all the gas Stations.
Consider the example: Here we have $g = (20, 40, 80, 10, 20)$ and $p = (0, 5, 13, 33, 36)$ (in kilometers). In order to send one gas-can from station 3 to station 4 we need to put 41 gas-cans in the truck, as the fueling-truck will consume 40 before reaching their destination (to send two gas-cans we need to put 42 in the truck). The optimal $\bar g$ for the example is 21 and can be achieved as follows:
Station 2 sends 11 gas-cans towards Station 1. One gas-can arrives while ten are consumed on the way.
Station 3 sends 59 gas-cans towards Station 4. 19 arrive while 40 are consumed on the way.
Station 4 now has 29 gas-cans and send eight towards Station 5. Two of these arrive and six are consumed on the way.
The final distribution of gas-cans is: $(21, 29, 21, 21, 22)$.
Greedy problem:
Given an integer $\bar g$. Consider we have an algorithm that determines whether it is possible to get at least $\bar g$ gas-cans in every Gas Station.
in order for the greedy choice property and optimal substructure to make sense for a decision problem, you can define an optimal solution to be a solution with at least $\bar g$ gas-cans in every gas station if such a solution exists; otherwise, any solution is an optimal solution.
Consider the Gas stations in increasing order; for Station $i < n$, either it needs gas-cans from Station $i + 1$ or it may have a surplus of gas-cans for Station $i + 1$.
Input: The position $p_i$ and gas-can supply $g_i$ of each bar. Here $g_i$ is the supply for the bar at position $p_i$. You may assume that the positions are in sorted order – i.e. $p_1 < p_2 < . . . < p_n$.
Output: The largest amount $\bar g$, such that each gas-station can have a gas-can supply of at least $\bar g$ after the truck have transferred gas-cans between the stations.
How can i prove that this problem exhibits greed choice property and optimal substructure?