CODEWITHSUNDEEP
algorithmdata-structuresdynamic-programmingcomputer-sciencegreedy
Marcus F
Marcus F

Reputation: 535

Showing that Greedy algorithm exhibits optimal substructure and greedy choice

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 g_bar they can have at all 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 g_bar for the example is 21 and can be achieved as follows:

  1. Station 2 sends 11 gas-cans towards Station 1. One gas-can arrives while ten are consumed on the way.

  2. Station 3 sends 59 gas-cans towards Station 4. 19 arrive while 40 are consumed on the way.

  3. Station 4 now has 29 gas-cans and send eight towards Station 5. Two of these arrive and six are consumed on the way.

  4. The final distribution of gas-cans is: (21, 29, 21, 21, 22).

Given an integer g_bar. Determine whether it is possible to get at least g_bar 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 g_bar gas-cans in every gas station if such a solution exists; otherwise, any solution is an optimal solution.

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 g_bar, such that each gas-station can have a gas-can supply of at least g_bar after the truck have transferred gas-cans between the stations.

How can i prove Greedy Choice and Optimal Substructure for this?

Upvotes: 2

Views: 424

Answers (1)

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

Let's define an optimal solution: Each station has at least X gas cans in each station (X = g_bar).

Proving greedy property

Let us assume our solution is sub-optimal. There must exist a station i such that gas[i] < X. Based on our algorithm, we borrow X - gas[i] from station i+1 (which is a valid move, since we had already found a solution). Now station i has gas = X. This contradicts the original assumption that there must exist a station i such that gas[i] < X, which means our solution isn't suboptimal. Hence, we prove the optimality.

Proving optimal substructure

Assume we have a subset of the stations of size N', and our solution is suboptimal. Again, if the solution is suboptimal, there must exist a station i such that gas[i] < X. You can use the greedy proof again to prove that our solution isn't suboptimal. Since we have optimal solution for each arbitrary subset, we prove that we have optimal substructure.

Upvotes: 1

Related Questions