寻求关于“鞋匠”问题的一般解决方案证明

Question

我遇到了这个问题：

一个鞋匠有N个工作（客户订单）要执行。

鞋匠一次只能处理一个工作。对于每个工作i，T[i]（1≤T[i]≤1000）是鞋匠完成该工作需要的时间（天数）。在开始工作之前每天延迟都要支付S[i]美分的罚款（1 ≤ S [i] ≤ 10000）。您的任务是帮助鞋匠找到总罚款最小的工作序列。

解决方案根据以下方法排序：S[i]/T[i]。不使用浮点数！

有人可以详细解释一下吗？我知道我们必须先完成T低、S高的工作，我也知道对于某些输入可能会起作用，但有人可以证明按S[i]/T[i]排序适用于一般情况吗？

- Styg

---

不要使用浮点数！考虑到限制，64位变量是可以的。 - David Eisenstat

Answer 1

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

- kraskevich

Answer 2

假设反证法，存在一种最优的排序方式，并且它不是按照 S[i]/T[i] 排序的。 => 存在一对作业 i 和 j，使得 S[i]/T[i] > S[j]/T[j]，并且 j 在 i 之前执行。

考虑交换 i 和 j 的顺序会如何改变总罚款，从而与最初假设的最优排序相矛盾。

这足够了吗？还是需要我完善论证/详细阐述？

- mrwhite