patternMinor
Calculate $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ maximizes
Viewed 0 times
mathbba_iwithgeqb_imaximizesthatcalculatesumand
Problem
I have two datasets $A$ and $B$:
$A = \{1, 5, -34, 34.34323, -23.5444, 9.43, ....\}$
$B = \{-0.5, 44, -0.243, -3455, 2.22221, -23.23, ....\}$
Those datasets contain a big amount of "random" numbers (They are actually not random, but their source does not matter for this question). Both datasets always have the same size.
Now I need to calculate two numbers $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ reaches the biggest possible value.
For clarification: Say $a_3 \geq u$ but $b_3 < v$. Then $(a_3 + b_3)$ is not included in the sum. That is meant by $ a_i \geq u$ and $b_i \geq v$.
Does an algorithm for the solution to this problem already exist? If not, I am open for ideas.
$A = \{1, 5, -34, 34.34323, -23.5444, 9.43, ....\}$
$B = \{-0.5, 44, -0.243, -3455, 2.22221, -23.23, ....\}$
Those datasets contain a big amount of "random" numbers (They are actually not random, but their source does not matter for this question). Both datasets always have the same size.
Now I need to calculate two numbers $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ reaches the biggest possible value.
For clarification: Say $a_3 \geq u$ but $b_3 < v$. Then $(a_3 + b_3)$ is not included in the sum. That is meant by $ a_i \geq u$ and $b_i \geq v$.
Does an algorithm for the solution to this problem already exist? If not, I am open for ideas.
Solution
For each pair of elements, $(a_{i},b_{i})$, you can calculate the sum of all the $(a_j+b_j)$ where $a_{j}$ and $b_{j}$ are both greater than or equal to $a_{i}$ and $b_{i}$. So an algorithm could look like:
This algorithm is $O(n^2)$ but is easily adaptable to n-variables, and there should be some shortcuts that could speed it up
largest_pair = 0
largest_value = -∞
for each i:
for each j:
total = 0
if(a[j] >= a[i] & b[j] >= b[i])
total += a[j] + b[j]
if(total>largest_value)
largest_value = total
largest_pair = i
u = a[largest_pair]
v = b[largest_pair]
output u,vThis algorithm is $O(n^2)$ but is easily adaptable to n-variables, and there should be some shortcuts that could speed it up
Code Snippets
largest_pair = 0
largest_value = -∞
for each i:
for each j:
total = 0
if(a[j] >= a[i] & b[j] >= b[i])
total += a[j] + b[j]
if(total>largest_value)
largest_value = total
largest_pair = i
u = a[largest_pair]
v = b[largest_pair]
output u,vContext
StackExchange Computer Science Q#67820, answer score: 4
Revisions (0)
No revisions yet.