Looking for a common proof of solution for the "Shoemaker"
I faced this problem:
The shoemaker has N tasks (orders from clients) to complete.
A shoemaker can only work one job each day. For each task i, T [i] (1≤T [i] ≤1000) is the time during which the shoemaker must complete the job. For each day of delay, before starting work i, the shoemaker must pay a fine S [i] cents (1≤S [i] ≤10000). Your task is to help the shoemaker find a sequence of tasks with a minimum result well.
The solution simply says:
Sort by S [i] / T [i]. Don't use floats!
Can anyone elaborate on the solution? I get that we need to do the low T and high S jobs first, and I see how for some inputs this will work, but can anyone demonstrate that sorting by S [i] / T [i] works in general case?
source to share
The proof looks like this: let's say that the order of the tasks has been corrected in some way. Let me take a look at two related tasks. If we change them, the answer to the tasks before these two and after these two will not change. This way, we can ignore all other assignments and see what happens if we replace these two as if we weren't different. If they are not replaced, the penalty is f1 = s1 * t1 + (t1 + t2) * s2
. If they swap places, it is f2 = s2 * t2 + s1 * (t1 + t2)
. In the optimal answer f1 <= f2
, which means s2 * t1 <= s1 * t2
, or s1 / t1 >= s2 / t2
. This comparator is transitive, so the optimal local ordering gives the optimal global answer.
source to share
Suppose the contrary, that it exists by optimal ordering and is not ordered by S [i] / T [i]. => There are several tasks i and j such that S [i] / T [i]> S [j] / T [j] and j is executed before i.
Consider how the overall tone will change by switching the order of i and j, contradicting the original assumption about the optimality of such an ordering.
Is this enough, or do you need me to finish the argument / elaborate?
source to share