将数组划分为相等的大小,以使给定函数的值最小

Question

我遇到了以下问题陈述.

您有一个自然数量大小的列表,N您必须将值分配到两个列表A和B大小中N/2,以便A元素的平方和最接近元素的乘法B.

示例: 考虑清单7 11 1 9 10 3 5 13 9 12.
优化分布为:
列表A:5 9 9 12 13
列表B:1 3 7 10 11
导致差值abs((5 + 9 + 9) + 12 + 13)^ 2 - (1*3*7*10*11))= 6
因此,您的程序应输出6,这是可以达到的最小差异.

我尝试过的:

我试过贪婪的方法来解决这个问题.我拿了两个变量sum和mul.现在我开始逐个从给定的集合中获取元素,并尝试在变量和计算的当前平方和和乘法中添加它.现在最终确定两组中的一组中的元素,使得组合给出最小可能值.

但是这种方法在给定的示例itselt中不起作用.我无法弄清楚这里可以使用什么方法.

我不是要求解决方案的确切代码.任何可能的方法及其工作原因都没问题.

编辑:

来源:CodinGame,社区谜题

Answer 1

我不确定多项式时间内是否有精确解。但您可以尝试基于模拟退火的方法。

我的方法是：

1. 将listA和listB初始化为随机状态
2. 以概率 p 运行贪婪步骤，否则运行随机步骤
3. 跟踪状态和相应的错误（使用 HashMap）

贪婪步骤：找到一个可以在列表之间移动的元素来优化错误。

随机步骤：从这两个集合中选择一个随机元素并计算误差。如果错误更好，则保留它。否则以 q 的概率保留它。

在这两个步骤中的任何一个步骤中，请确保尚未探索新状态（或至少阻止它）。

将 p 设置为一个较小的值 (<0.1)，q 可能取决于误差差异。