3

我有以下问题：

给定一组变量和，例如 { a + b, b + c, c + d, a + a + d, b }，找到变量的正整数值，使得所有和都不同并且最大和一样小尽可能。

是否有一种算法可以找到或近似解决此类问题？

4

1 回答 1

1

我在 C# 中创建了一个可能的解决方案和一个实现。希望这是你需要的。如果有人证明它是正确/不正确的，但它有效并且结果看起来正确，那就太好了。理论细节如下。它的复杂性是关于O(N!*M^3*Log2(N))哪里N是变量M的数量和是所有和的总和的数量。

顺便说一句，对于您的示例，它给出了以下结果：

c=3, a=2, d=2, b=1
{a+b=3; b+c=4; c+d=5; a+a+d=6; b=1}
max=6

更新

算法理论。

假设变量是有序的，例如，a >= b >= c >= .... 假设一组总和是一个Bag ，如​​果其中的所有总和都是不同的。Bag 中的所有总和可以分为两组：不包含变量a的总和和包含变量的总和。让我们将第一组称为Head，将第二组称为Tail。请注意，两者都是 Bags，因为它们包含不同的总和。我们可以a从 Tail 中的每个总和中减去，以便所有总和保持不同（即 Tail 仍然是 Bag）。这样我们就得到了两个没有变量的包a。

类似的方式，我们从两个包中排除变量b并得到四个包。我们对每个变量重复这个操作，直到我们得到最后一个变量的总和（假设它是d）。的最小值d为 1。

之后，我们可以返回上一步并将变量包含c在尾部的总和中。请记住，我们有很多头尾对，需要将它们重新加入。为此，我们将c每个 Tail 中的每个总和相加，因此 Tail 的总和必须与 Head 不同。

如何计算c？这个想法是计算其无效值，然后取非无效且等于或大于的最小值d。使用条件=>计算无效值是微不足道的。对于尾和和头和的每个组合，我们得到所有无效值。HeadSum != TailSum + cc != HeadSum - TailSum

折叠所有对 Head-Tail 并计算每个变量，我们得到了 case 的解决方案a >= b >= c >= d。然后我们计算每个排列的解a >= b >= c >= d并找到最小的一个。

PS如果有人提供更好的解决方案会很棒，因为我认为我的算法有点近似（但很好的近似）甚至更好地证明它。最糟糕的是N!由于排列而导致的复杂性，我仍然不知道如何摆脱它。

于 2014-12-04T10:11:19.643 回答