c# - 如何找到段的组合来构建轨道 : possible Subset Sum

Question

SO 上有很多子集求和问题和答案，但不知何故我找不到解决我的特定问题的方法。

我需要找到轨道段的数量和长度来构建长度为 n 的轨道。这些段的长度为:8、10、12、14、16、18、20、22、24 英尺数量最多可达4段轨道长度大约在 20 到 100 英尺之间(并且始终为偶数)

这是一条真实的轨道。段的顺序无关紧要。然而，存在优选的尺寸组合。与大/小组合相比，所有长度相等或彼此接近的是首选。

即:

• 70 => 20,20,20,10 是一个简单的选择，但首选 16,18,18,18
• 60 => 20,20,20 优于 14,14,14,18

如果需要，我可以提供更多示例。

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

到目前为止，我所做的如下。它正在工作，只是看起来很复杂。

我从这篇文章中获取了基本算法 Algorithm to find which numbers from a list of size n sum to another number .我在这段代码中所做的改变就是把它变成整数。它返回所有可能的组合。最多 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:

或者用 80 这个

    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 和 5)实际上接近我的需要。

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

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

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

Answer 1

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

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

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