0

I have recieve as input a list of candidates for work so that the list I recieve is already sorted by requirments of the salary for each one and also is grase from the university(this parameter is not sorted). example:

danny 13000$ 75.56

dan 9000$ 100

bob 5000$ 98

in such a list I need to find the two candidates with the higher grades so that sum of both salary is not more than 10000$ (I can assume their is no two candidates with the same grade and there are no two pair of students with the same sum of grade (94+90 = 91 + 93))

I need to find them in comlexity of O(n).

I understand I can not do a sort algorithm (the min is n*log(n)) so How can I do that ?

is it possible ?

4

2 回答 2

1

O(n)解决方案（假设数字 10,000 是固定的）：

arr <- new empty array of size 10000
for each i from 1 to 10000:
   arr[i] = "most valuable" worker with salary up to i
best <- -infinity
for each i from 1 to 5000:
   best = max{ best, arr[i] + arr[10000-i]}
return best

这个想法是保存一个数组，在每个条目中，您保存最多要求该薪水的“最佳”候选人（这是在第一个循环中完成的）。

在第二个循环中，您检查所有可行的可能性并找到最大值。

请注意，第一个循环的天真方法是O(n)使用可怕的常量（每次迭代都是O(n)，并且完成了 10,000 次）。但是，您可以arr通过从最低工资开始使用 DP 进行构建，并执行以下操作：

arr[i] = max {arr[i-1], best worker with salary i}

DP 解决方案O(n)只遍历数组一次（或正式的最大工资O(W+n)在哪里W）。

另请注意 - 这是背包问题的私人案例，只能选择 2 个元素。

于 2012-12-27T11:22:24.320 回答
1

因为它是按薪水排序的，从两个指针开始。i 指向起点（最低销售额），j 指向最高销售额。现在，当销售量超过限制时，减少 j。现在增加 i 并减少 j 保持在限制以下。跟踪 i 和 j 的最高等级。

于 2012-12-27T11:30:21.107 回答