如何找到分段的组合来构建轨道:可能的子集和

我们把所有的都除以2，因为所有的都是偶数。我们现在有长度为4到12的轨道件，总长度约为10到50。

Name n我们必须达到的长度。对于每一个轨道片k的可能数量(一般为1到4，但n<16为1到3，例如>n>36为3到4)，建议取n%k长度n/k+1和k-n%k长度n/k的片。

'/'表示整数除法，'%'表示余数。

你真的有一个和集的特殊情况。虽然它是np困难的，但解决方案空间受到足够的限制，因此蛮力可能会很好地工作，因为总共只有10000(10 ^ 4)个可能的解决方案(大约等于所需的实际时间步数)，因为您还必须考虑0作为可能的长度。

下面是代码，使用psudo-Python。考虑过在c#中尝试，但实际上不熟悉它，所以它可能不会很好地工作。

lengths = [0, 8, 10, 12, 14, 16, 18, 20, 22, 24]
solutions = []
for len1 in lengths:
    for len2 in lengths:
        for len3 in lengths:
            for len4 in lengths:
                if (len1 + len2 + len3 + len4) == n:
                    solutions.append([len1,len2,len3,len4])
return solutions

一旦你有了所有有效的解决方案，你就可以简单地决定你想向用户展示哪一个(s)，或者你可以简单地编写一个算法来选择最好的一个。当然，您可能不希望实际包含任何长度为0的元素。

你可以使用贪心方法来改进这个算法，它只会找到所有有效的解。然而，同样的，正如它所陈述的问题不太可能复杂到需要它，除非事情在空间或时间方面非常有限。

作为额外的好处，如果您期望多个查询(例如用户请求n = 40，然后请求n = 50)，您可以删除if语句，并简单地将所有10000个解决方案存储在与sum值键合的哈希表中，从而允许O(1)个查询。

缩小解决方案集:

这里你需要的是一个比较算法，它将这个解决方案与那个解决方案进行比较，并说"这个解决方案比那个解决方案好/坏"。这允许你编写一个排序算法，你可以用它来对解决方案进行排序，以得到最好的，或者你可以简单地找到最好的解决方案。

您可以通过简单地计算每个解决方案的标准偏差然后比较标准偏差来解决绝大多数情况。这将给出一个数字，显示解决方案长度的方差有多大。如果你使用"更低的标准偏差更好"，那么你就会得到"所有长度相等或彼此接近的组合比大/小组合更受欢迎"。标准偏差的算法相当简单，所以我把它留给你们自己去实现。实际上，c#很有可能内置了这个函数。只是要确保不包含任何零长度，实际上它们应该在您将它们添加到解决方案集之前被删除，以避免问题，这需要对我给出的代码进行一些调整。

然而，你有一个棘手的部分，处理不同的解决方案有相同的标准差的情况。我认为只有两种情况会发生这种情况。

1. 第一种情况只存在多个理想解决方案。如n = 24，则有三个解为[8,8,8]，[12,12]和[24]。

2. 第二个是由于算法的蛮力性质，这就是为什么有这么多的解决方案。这是因为对于像[8,10,12,14](四个唯一的长度)这样的每个解，有24种排列这些长度的方法，比如[14,12,10,8]和[12,10,14,8]。因此，改进蛮力算法的最佳方法是使用一种算法，从[0,8,10,12,14,16,18,20,22,24]中选择4个元素。这将解决方案集缩小到只有715个解决方案。当然，如果你真的想要[8,10,12,14]，[14,12,10,8]和[12,10,14,8]作为不同的解决方案，那么你就无能为力了。

以上两段完全属于"视情况而定"的范畴。你必须决定每种情况下算法应该遵循什么规则，但我认为这是你能找到相同标准差的唯一两种情况。

数学来拯救!

你可以检查每一个大于8的偶数都是这个集合中元素的线性组合——向Math Overflow寻求证明;)。

那么让我们用数学来表达这个问题:

• 我们有一个基向量的过完备字典(因为16，例如，是8的倍数)，
• ，其中我们可以将大于8的偶数表示为这些基向量的线性组合，并且
• 我们试图最小化这个输入向量的零"范数"。

好消息:这是一个非常有趣的问题，涉及许多应用领域，因此研究得相当充分。

坏消息是:这仍然是一个很难的(NP-hard)问题。

但是，嘿，至少现在你知道了。

为了不让别人指责我给出了一个哲学式的答案，这里有一个修改过的(完全没有优化过的)Solver.recursiveSolve版本，它详尽地搜索符合目标的片段组合;还有一个零规范比较类，您可以使用它对结果进行排序:

    private void RecursiveSolve(int goal, int currentSum,
        List<int> included, List<int> segments, int startIndex)
    {
        for (int index = 0; index < segments.Count; index++)
        {
            int nextValue = segments[index];
            if (currentSum + nextValue == goal)
            {
                List<int> newResult = new List<int>(included);
                newResult.Add(nextValue);
                mResults.Add(newResult);
            }
            else if (currentSum + nextValue < goal)
            {
                List<int> nextIncluded = new List<int>(included);
                nextIncluded.Add(nextValue);
                RecursiveSolve(goal, currentSum + nextValue,
                    nextIncluded, segments, startIndex++);
            }
        }
    }
class ZeroNormAndSDComparer : IComparer<List<int>>
{
    private int l0_norm(List<int> v)
    {
        int norm = 0;
        HashSet<int> seen = new HashSet<int>();
        for (int i = 0; i < v.Count; ++i)
        {
            if (!seen.Contains(v[i]))
            {
                norm++;
                seen.Add(v[i]);
            }
        }
        return norm;
    }
    private static double StandardDeviation(List<int> v)
    {
        double M = 0.0;
        double S = 0.0;
        int k = 1;
        foreach (double value in v)
        {
            double tmpM = M;
            M += (value - tmpM) / k;
            S += (value - tmpM) * (value - M);
            k++;
        }
        return Math.Sqrt(S / (k - 1));
    }
    public int Compare(List<int> x, List<int> y)
    {
        int normComparison = l0_norm(x).CompareTo(l0_norm(y));
        if  (normComparison == 0)
        {
            return StandardDeviation(x).CompareTo(StandardDeviation(y));
        }
        return normComparison;
    }
}

和修改后的Main(现在排序是在结果减少到不同的4段结果后完成的):

        List<int> nums = new List<int>() { 8, 10, 12, 14, 16, 18, 20, 22, 24 };
        int width = 80;
        Console.WriteLine("Total width: " + width);
        Solver solver = new Solver();
        List<List<int>> res = solver.Solve(width, nums.ToArray());
        Console.WriteLine("total :" + res.Count);
        var res1 = res.Distinct(new SequenceComparer<List<int>, int>()).ToList();
        Console.WriteLine("total res1:" + res1.Count);
        var res2 = res1.Where(l => l.Count == 4).ToList();
        Console.WriteLine("total res2:" + res2.Count); //reduce to 4 integer solutions
        res2.Sort(new ZeroNormAndSDComparer());