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

Question

SO有很多关于子集和的问题和答案，但不知怎么的，我找不到解决我具体问题的方法。

我需要找到轨道段的数量和长度，以构建长度为n的轨道。轨道段的长度为：8、10、12、14、16、18、20、22、24英尺。数量最多可为4个轨道段。轨道长度在20到100英尺之间（且始终为偶数）

这是一条真正的赛道。分段的顺序并不重要。但是，也有首选的尺寸组合。与大/小组合相比，所有长度相等或彼此接近的组合都是首选。

即：

• 70=

如果需要，我可以列举更多的例子。

我不是在寻找一个最好的解决方案，而是一组可能的最佳解决方案。最终一个人会选择，这是关于建议的最佳选择。

到目前为止，我做了以下几点。它正在发挥作用，只是看起来很复杂。

我从这篇文章中的基本算法算法中找到了从大小n和的列表中的哪些数字到另一个数字。我在这段代码中所做的只是把它变成整数。它返回所有可能的组合。多达5个或更多的轨道。

为了进一步减少结果集，我做了一些Linq

    List<int> nums = new List<int>() { 8, 8, 8, 8, 10, 10, 10, 10, 12, 12, 12, 12, 14, 14, 14, 14, 16, 16, 16, 16, 18, 18, 18, 18, 20, 20, 20, 20, 22, 22, 22, 22, 24, 24, 24, 24 };
    int width = 60;
    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

    var res3 = (from row in res2
             where row[0] == row[1] || row[0] == row[2] || row[0] == row[3] ||
                   row[1] == row[2] || row[1] == row[3] ||
                   row[2] == row[3]
             select row).ToList();
    Console.WriteLine("total res3:" + res3.Count); //reduce to at least two of equal length

    var res4 = (from row in res3
            where row[0] == row[1] && row[0] == row[2] || 
                  row[0] == row[1] && row[0] == row[3] ||
                  row[1] == row[2] && row[1] == row[3] 
            select row).ToList();
     Console.WriteLine("total res4:" + res4.Count); //reduce to  three of equal length

    var res5 = (from row in res4
            where row[0] == row[1] && row[0] == row[2] && row[0] == row[3]
           select row).ToList();

     Console.WriteLine("total res5:" + res5.Count); //reduce to 4 of equal length
     Console.WriteLine("-------------------------------------");
     Console.WriteLine("res4:");
     foreach (List<int> result in res4)
     {
         foreach (int value in result)
         {
              Console.Write("{0}\t", value);
         }
         Console.WriteLine();
      }
      Console.WriteLine("-------------------------------------");
      Console.WriteLine("res5:");
      foreach (List<int> result in res5)
      {
           foreach (int value in result)
           {
               Console.Write("{0}\t", value);
           }
           Console.WriteLine();
      }
      Console.ReadLine();

这段代码将产生以下结果，以60

    Total width: 60
    total :10726
    total res1:74
    total res2:31
    total res3:20
    total res4:3
    total res5:0
    -------------------------------------
    res4:
    12      12      12      24
    12      16      16      16
    14      14      14      18
     -------------------------------------
    res5:

还是用这个

    Total width: 80
    total :101560
    total res1:237
    total res2:15
    total res3:13
    total res4:3
    total res5:1
    ------------------------------------
    res4:
    8       24      24      24
    14      22      22      22
    20      20      20      20
    ------------------------------------
    res5:
    20      20      20      20

所以我的最终结果（4）

但对于任何可能的3轨解决方案，可能还有2轨，我都必须再次编写相同的代码。

那么结果是否需要相互比较（不知何故，不确定如何比较）。所有这些让我觉得我错过了什么。感觉很复杂，感觉很不对。我错过了什么？

我是不是一开始就用错了算法？他们解决我的问题后会更好吗？

Answer 1

数学救援！

您可以检查每个大于8的偶数是否是此集合中元素的线性组合-请在Math Overflow上获取证明；）。

所以让我们换个数学问题：

• 我们有一个基向量的超完备字典（例如，因为16是8的倍数），

好消息是：这是一个非常有趣的问题，有许多应用程序领域，所以研究得很好。

坏消息是：这仍然是一个难（NP难）问题。

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

编辑：为了不让我被指责为手握哲学答案，这里有一个改进版（完全未优化）的Solver。递归求解，彻底搜索与目标匹配的段组合；以及一个零范数比较器类，您可以使用它对结果进行排序：

    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());

Answer 2

你真的有求和集的一个特例。虽然它是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

一旦你有了所有有效的解决方案，你就可以简单地决定你想给用户看哪一个，或者你可以简单地写一个算法来选择最好的一个。当然，你可能不想包括任何大小为0的长度。

您可以使用贪心方法对该算法进行一些改进，该方法只能找到所有有效的解决方案。然而，同样地，这个问题不太可能复杂到需要它，除非事情在空间或时间方面非常有限。

作为奖励，如果您希望进行多个查询（例如，用户要求n=40，然后n=50），您可以删除if语句，只需将所有10000个解决方案存储在一个哈希表中，该哈希表设置为sum值，允许进行O（1）查询。

缩小解决方案集的范围：

这里你需要的是一个比较算法，它基本上把这个解决方案和那个解决方案进行比较，并说，“这个解决方案比那个解决方案好/最差”。这允许你编写一个排序算法，你可以用它来对解决方案进行排序，以获得最好的解决方案，或者你可以简单地找到最好的解决方案。

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

然而，你接下来有棘手的部分，处理不同解决方案具有相同均方差的情况。我认为只有两种情况会发生这种情况。

>

第一种情况只有存在多个理想解，例如如果n=24，那么其中三个解将是[8,8,8]，[12,12]，和[24]。

第二种情况是由于算法的蛮力性质，这也是为什么有这么多解决方案。这是因为对于像[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]作为不同的解决方案，那么你就无能为力了。

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

Answer 3

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

说出我们必须达到的长度。对于每k个可能的轨道件（一般为1到4个，但n为1到3个）

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