algorithm - 寻求 "Shoemaker"解决方案的一般证明

Question

我遇到了这个问题:

A shoemaker has N jobs (orders from customers) to execute.

The shoemaker can work on only one job each day. For each job i, T[i] (1≤T[i]≤1000) is the time in days it takes the shoemaker to finish the job. For each day of delay before starting to work on job i, the shoemaker must pay a fine of S[i] cents (1≤S[i]≤10000). Your task is to help the shoemaker to find the sequence of jobs with minimal total fine.

解决方案简单地说:

Sort by S[i]/T[i]. Do not use float!

有人可以详细说明解决方案吗？我知道我们必须首先处理低 T 和高 S 的工作，我知道这对于某些输入是如何工作的，但是有人可以证明按 S[i]/T[i] 排序在一般情况下有效吗？

Answer 1

证明看起来像这样:让我们假设作业的顺序是固定的。让我们来看看两个相邻的工作。如果我们交换它们，这两个之前和之后的工作的答案不会改变。所以我们可以忽略所有其他工作，看看如果我们交换这两个工作会发生什么，就好像我们没有其他工作一样。如果他们不交换，罚款是f1 = s1 * t1 + (t1 + t2) * s2 .如果交换，则为f2 = s2 * t2 + s1 * (t1 + t2) .在最佳答案f1 <= f2 , 这意味着 s2 * t1 <= s1 * t2 , 或 s1 / t1 >= s2 / t2 .这个比较器是可传递的，因此最优的局部排序给出了最优的全局答案。