Here's a problem solvable by greedy algorithm:
You are a company and you have list of tasks that still need to be done (but you're late with them already). For a given task we have information about required days to finish it and how much money we need to pay for every day we're late (so for example if we're at day 6. and we're now doing the task which requires 4. days and the penalty for one day is 500\$, then doing this task costed us $(6+4)*500\$$).
The problem is to find optimal order of doing the tasks in order to minimize total penalty paid by the company.
Apparently it can be done by sorting all tasks by (days required to finish the task)/(penalty for 1 day) and returning the sorted order. I thought that the exchange argument should be enough to prove that this is correct.
So we assume that there exists optimal task order where tasks are not sorted using the rule above. Then for some indices $i,j$ where $j>i$ we have $\frac{d_i}{p_i}>\frac{d_j}{p_j}$ (where $d_k$ are days required to do task on k-th position and $p_k$, penalty for one day delay). So the money paid by the company for tasks i-j is:
$$\$_{i,j}=d_ip_i+(d_i+d_{i+1})p_{i+1}+…+(d_i+d_{i+1}+…+d_{j-1}+d_j)p_j$$
Now the natural move would be to exchange task i with task j and calculate money paid by company then:
$$\$'_{i,j}=d_jp_j+(d_j+d_{i+1})p_{i+1}+…+(d_j+d_{i+1}+….+d_{j-1}+d_i)p_i$$
Now if we showed that $\$'_{i,j}\leq\$_{i,j}$ using assumption earlier we would be home. The problem is when we subtract:
$$\$_{i,j}-\$'_{i,j}=(d_i-d_j)d_{i+1}+(d_i-d_j)d_{i+2}+…+(d_i-d_j)d_{j-1}+(d_i+…+d_{j-1})p_j+(d_{i+1}+…+d_j)p_i$$
I see nothing. What should I do now in order to finish the proof? I know this sum must be non-negative but how to "discover" that?
Best Answer
Take two tasks next to each other.
Perform $i$ then $j$, you will pay $p_id_i+p_j(d_i+d_j)$.
Perform $j$ then $i$, you will pay $p_i(d_i+d_j)+p_jd_j$.
The other costs are unchanged. The sign of the difference $p_id_j-p_jd_i=\left(\frac{d_j}{p_j}-\frac{d_i}{p_i}\right)p_ip_j$ tells you to swap or not.
If you keep doing this until there are no more swappable pairs, in the end the list will be sorted by decreasing $d/p$. Conceptually, the above procedure resembles a Bubblesort, but what matters is the final sorted state, so swaps may be performed by any sorting algorithm.
Note that Insertionsort and Selectionsort can be seen as two forms of greedy sorting algorithms: Insertionsort aggregates a sorted sequence and inserts new elements into it one by one, Selectionsort aggregates a sorted sequence and appends new elements to it one by one.