在工作中实现利润最大化
Maximizing profit in doing the jobs
我们有两个整数数组 M（金钱）和 E（经验），每个数组的大小最多为 50。 Bob 完成第 i 个工作后，会发生两件事：
（设 TE 为 Bob 由 0 初始化的总经验）
- Bob 的经验（即
TE）增加 E[i]
- 那么，他将收到等于
TE*M[i] 的钱
如果 Bob 以最佳顺序完成工作，他可以获得的最大利润是多少？
For any i we know:
1 <= E[i] <= 10^5
1 <= M[i] <= 10
Example:
M[] = { 20, 30, 100 }
E[] = { 1, 1, 6 }
Answer: 880 = job 3-1-2 = 6*100 + 7*20 + 8*30 = 980
我认为这个问题可以通过贪心算法（DP的一个特例）来解决，如下所述：
- 按比例
Exp/Money 降序排列作业
- 如果平局，则按
Money 升序 对作业进行排序
那么排序后的作业顺序就是产生最优解的作业顺序。
我的推理如下：比率Exp/Money可以解释为1钱可以买多少Exp，所以我们选择总是更好先做比例高的职业，这样可以增加后期职业的经验。
在平局的情况下，选择金钱奖励较小的工作，因为这使得金钱奖励较高的工作以后可以乘以较大的经验系数。
例如：
E = {2,1,6,1}
M = {40,20,100,10}
Sorted job = { job3, job4, job2, job1}
= 6*100 + 7*10 + 8*20 + 10*40 = 1230
我们有两个整数数组 M（金钱）和 E（经验），每个数组的大小最多为 50。 Bob 完成第 i 个工作后，会发生两件事：
（设 TE 为 Bob 由 0 初始化的总经验）
- Bob 的经验（即
TE）增加E[i] - 那么，他将收到等于
TE*M[i]的钱
如果 Bob 以最佳顺序完成工作，他可以获得的最大利润是多少？
For any i we know:
1 <= E[i] <= 10^5
1 <= M[i] <= 10
Example:
M[] = { 20, 30, 100 }
E[] = { 1, 1, 6 }
Answer: 880 = job 3-1-2 = 6*100 + 7*20 + 8*30 = 980
我认为这个问题可以通过贪心算法（DP的一个特例）来解决，如下所述：
- 按比例
Exp/Money降序排列作业 - 如果平局，则按
Money升序 对作业进行排序
那么排序后的作业顺序就是产生最优解的作业顺序。
我的推理如下：比率Exp/Money可以解释为1钱可以买多少Exp，所以我们选择总是更好先做比例高的职业，这样可以增加后期职业的经验。
在平局的情况下，选择金钱奖励较小的工作，因为这使得金钱奖励较高的工作以后可以乘以较大的经验系数。
例如：
E = {2,1,6,1}
M = {40,20,100,10}
Sorted job = { job3, job4, job2, job1}
= 6*100 + 7*10 + 8*20 + 10*40 = 1230