如何在给定的对值中找到多个对，使它们的第一个值的总和乘以第二个值的总和达到最大值

Question

如何实现该算法：从大约 5,000 对中选择 15 对，将这些对的第一个值相加，将第二个值相加，然后将两个结果相乘以使结果最大化。 例如 有 10 对 (1,1),(2,2),(3,3),(4,2),(5,2),(4,3),(7,1),(2,9 ),(10,1),(2,10); 选择 5 对 (4,3),(7,1),(2,9) (10,1),(2,10)； 第一个总和是 25 ，第二个总和是 24 。 所以答案是600。 可以证明这是最优组合。

我考虑了一些算法，比如如果一对中的第一对和第二对完全大于另一对，那么你可以排除较小的对。 如果某些对的第一和第二的和相同，例如（4,2），（3,3），那么选择（3,3）将使结果更大，因为相同周长的正方形的面积更大比长方形的面积。 所以我最初的想法是取 15 对，以某种顺序对这 15 对进行排序，找到对结果贡献最小的对，然后迭代剩余的 4985 对以获得最大值， 但是我觉得这种贪心策略不会得到最优解，它会得到一个相对好的解，因为例如，如果你排除 (1,10) 但如果你有一个 (10,1) 组合，那么这两个他们在一起将是一个不错的选择， 所以我认为使用某种动态编程思想似乎是一个更好的选择，但是我不知道应该使用什么动态编程方法，我希望有人可以解决我的问题。

Answer 1

这是一个简单的方法，对于从 5000 对中选择 15 对来说应该足够快。

我们将输入称为 5000 对，P。

创建一个数组 A 并用 P 中的前 15 对填充它。跟踪 A 的第一个 elt 的总和以及第二个 elt 的总和。

然后，对于 P 中剩余的每一对，检查如果我们将其与 A 的每个值交换，A 的值会是多少，如果有改进，则进行能产生最佳改进的交换。

这对于从 5000 对中挑选最好的 15 对来说应该非常有效。

这是 Ruby 代码来说明这个想法

def f(pairs, output_size = 15)
  
  # Initialize the answer to the first output_size (15) elts of the pairs array
  ans = pairs[0, output_size]
  
  # Calculate the two sums for the initialized ans array
  left_sum = 0
  right_sum = 0
  0.upto(output_size - 1) do |i|
    left_sum += pairs[i][0]
    right_sum += pairs[i][1]
  end
  
  output_size.upto(pairs.length - 1) do |i|
    test_left = pairs[i][0]
    test_right = pairs[i][1]
    best_swap_index = -1
    best_swap_result = left_sum * right_sum
    
    0.upto(ans.length - 1) do |j|
      ans_left = ans[j][0]
      ans_right = ans[j][1]
      cur_swap_result = (left_sum - ans_left + test_left) * (right_sum - ans_right + test_right)
      if cur_swap_result > best_swap_result
        best_swap_index = j
        best_swap_result = cur_swap_result
      end
    end
    
    if i >= 0
      left_sum = left_sum - ans[best_swap_index][0] + test_left
      right_sum = right_sum - ans[best_swap_index][1] + test_right
      ans[best_swap_index] = pairs[i]
    end
  end
  
  
  puts "input:  #{pairs.to_s}"
  puts "result: #{ans.to_s}"
  puts "value:  #{left_sum * right_sum}"
  return nil
end

以下是您提供的示例输入的结果：

> f([[1,1], [2,2], [3,3], [4,2], [5,2], [4,3], [7,1], [2,9], [10,1], [2,10]], 5)
input:  [[1, 1], [2, 2], [3, 3], [4, 2], [5, 2], [4, 3], [7, 1], [2, 9], [10, 1], [2, 10]]
result: [[4, 3], [7, 1], [10, 1], [2, 9], [2, 10]]
value:  600