我遇到了这个问题:
一个鞋匠有N个工作(客户订单)要执行。
鞋匠一次只能处理一个工作。对于每个工作i,T[i](1≤T[i]≤1000)是鞋匠完成该工作需要的时间(天数)。在开始工作之前每天延迟都要支付S[i]美分的罚款(1 ≤ S [i] ≤ 10000)。您的任务是帮助鞋匠找到总罚款最小的工作序列。
解决方案根据以下方法排序:S[i]/T[i]。不使用浮点数!
有人可以详细解释一下吗?我知道我们必须先完成T低、S高的工作,我也知道对于某些输入可能会起作用,但有人可以证明按S[i]/T[i]排序适用于一般情况吗?
一个鞋匠有N个工作(客户订单)要执行。
鞋匠一次只能处理一个工作。对于每个工作i,T[i](1≤T[i]≤1000)是鞋匠完成该工作需要的时间(天数)。在开始工作之前每天延迟都要支付S[i]美分的罚款(1 ≤ S [i] ≤ 10000)。您的任务是帮助鞋匠找到总罚款最小的工作序列。
解决方案根据以下方法排序:S[i]/T[i]。不使用浮点数!
有人可以详细解释一下吗?我知道我们必须先完成T低、S高的工作,我也知道对于某些输入可能会起作用,但有人可以证明按S[i]/T[i]排序适用于一般情况吗?