6

我这里真的需要一个算法大师！所以问题是我得到了一个这样的数组：

[
    [870, 23]
    [970, 78]
    [110, 50]
]

我想把它分开，使它看起来像这样：

// first array
[
    [970, 78]
]
// second array
[
    [870, 23]
    [110, 50]
]

所以现在，为什么我也想让它看起来像这样？

因为我想保持子值的总和尽可能相等。所以970是关于870 + 110和78是关于23 + 50。所以在这种情况下这很容易，因为如果你只是拆分它们并且只查看第一个子值它已经是正确的但我想检查两者并保持它们尽可能相等，这样它也可以使用一个包含 100 个子数组的数组！所以如果有人能告诉我我可以用什么算法来编程，那就太好了！

秤：

  • 数组中约 1000 个元素（子列表）
  • 元素是最大 10^9 的整数

我正在寻找一个“足够接近的解决方案” -它不一定是确切的最佳解决方案。

4

4 回答 4

2

首先，正如已经确定的那样 - 问题是NP-Hard，具有简化形式的分区问题。

减少： 给定一个分区问题
的实例，创建每个大小为 1 的列表。结果就是这个问题。

从上面得出的结论：
这个问题是NP-Hard，并且没有已知的多项式解决方案。

其次，由于问题的规模，任何指数和伪多项式解决方案都需要很长时间才能工作。

第三，它给我们留下了启发式算法和近似算法。

我建议采用以下方法：

  1. 标准化子列表的比例，因此所有元素都将处于相同的比例（例如，所有元素都将被标准化为范围[-1,1]或所有元素都将被标准化为标准正态分布）。
  2. 创建一个新列表，其中每个元素将是规范化列表中匹配子列表的总和。
  3. 使用为子集和/分区问题开发的一些近似或启发式解决方案。

结果不会是最优的，但最优在这里确实无法实现。

于 2012-10-28T19:42:01.683 回答
2

根据我从原始帖子下的讨论中收集到的信息，您不是在寻找单个分裂点，而是希望将所有对分布在两组之间，以使两组中的每一组的总和大致相等。

由于足够接近的解决方案是可以接受的，也许您可​​以尝试基于模拟退火的方法？（见http://en.wikipedia.org/wiki/Simulated_annealing）

简而言之，这个想法是您首先将每对随机分配到左集或右集。接下来，您可以通过以下任一方式生成一个新状态

  • a) 将随机选择的对从左侧移动到右侧集合，
  • b) 将随机选择的对从右侧移到左侧集合，或
  • c) 两者都做。

接下来，确定这个新状态是比当前状态更好还是更差。如果更好，请使用它。如果情况更糟，则仅在被接受概率函数接受时才接受，该函数最初允许使用更差的状态，但随着时间的推移（或“温度降低”，在SA 条款）。经过大量的迭代（比如 100.000 次），你应该会得到一个不错的结果。

或者，多次重新运行该算法，因为它可能会陷入局部最优（尽管接受概率函数试图解决这个问题）。

这种方法的优点是易于实现，您可以自行决定希望它继续寻找更好的解决方案多长时间。

于 2012-10-28T20:00:27.183 回答
1

我假设我们只是在数组中间寻找一个位置，将其分成第一部分和第二部分。

似乎线性算法可以做到这一点。JavaScript 中有类似的东西。

arrayLength = 2;
tolerance = 10;

// Initialize the two sums.
firstSum = [];
secondSum = [];
for (j = 0; j < arrayLength; j++)
{
   firstSum[j] = 0;
   secondSum[j] = 0;
   for (i = 0; i < arrays.length; i++)
   {
      secondSum += arrays[i][j];
   }
}

// Try splitting at every place in "arrays".
// Try to get the sums as close as possible.
for (i = 0; i < arrays.length; i++)
{
   goodEnough = true;
   for (j = 0; j < arrayLength; j++)
   {
      if (Math.abs(firstSum[j] - secondSum[j]) > tolerance)
         goodEnough = false;
   }

   if (goodEnough)
   {
      alert("split before index " + i);
      break;
   }

   // Update the sums for the new position.
   for (j = 0; j < arrayLength; j++)
   {
      firstSum[j] += arrays[i][j];
      secondSum[j] -= arrays[i][j];
   }
}
于 2012-10-28T19:39:17.010 回答
0

感谢所有答案，蛮力攻击是个好主意，NP-Hard 也与此有关，但事实证明这是一个多重背包问题，可以使用此 pdf 文档解决。

于 2012-11-02T06:39:13.697 回答