-1

我有一个括号列表，我需要找到它们的组合，最多 4 个括号，最适合某个长度。

这些是我的括号，例如，我需要找出最接近的这些组合，而不超过 120 英寸。

<?xml version="1.0" encoding="utf-8" ?>
<brackets>
  <bracket>
    <PartNumber>F0402583</PartNumber>
    <Length>42.09</Length>
  </bracket>
  <bracket>
    <PartNumber>F0402604</PartNumber>
    <Length>32.36</Length>
  </bracket>
  <bracket>
    <PartNumber>F0403826</PartNumber>
    <Length>46.77</Length>
  </bracket>
  <bracket>
    <PartNumber>F0402566</PartNumber>
    <Length>44.17</Length>
  </bracket>
  <bracket>
    <PartNumber>F0402289</PartNumber>
    <Length>20.55</Length>
  </bracket>
  <bracket>
    <PartNumber>F0402612</PartNumber>
    <Length>18.46</Length>
  </bracket>
  <bracket>
    <PartNumber>F0402606</PartNumber>
    <Length>30.28</Length>
  </bracket>
  <bracket>
    <PartNumber>F0403828</PartNumber>
    <Length>22.76</Length>
  </bracket>
</brackets>

我试图找出 SolverFoundation 库，但我不是数学专业的，对此几乎没有经验......使用 Excel Solver 和 Simplex LP 求解方法，解决方案是 1 30.28" 支架，1 42.09" 支架，和1 46.77" 支架，结果为 119.14"

4

1 回答 1

0

这是一个天真的解决方案。我对数学的理解也有限（最高级的是组合数学之类的！），所以我理解挑战。此解决方案遍历所有可能性，然后按有效解决方案（总长度 < 120 的解决方案）过滤，按长度对它们进行排序，并输出第一个结果。

我敢肯定，如果您的解决方案需要展示对某些数学概念的理解，那么这不是寻找解决方案的方法——但这将使您能够轻松地检查您的解决方案。

运行时间为 O(n^c)。

    public static void Main(string[] args)
    {
        var lengths = new List<decimal>(new decimal[] { 42.09m, 32.36m, 46.77m, 44.17m, 20.55m, 18.46m, 30.28m, 22.76m }); 
        var lst = new List<Solution>(); 
        for (int i = 0; i < lengths.Count; i++) { 
            lst.Add(new Solution(new decimal[] { lengths[i] }));  
            for (int j = 0; j < lengths.Count; j++) { 
                lst.Add(new Solution(new decimal[] { lengths[i], lengths[j] })); 
                for (int k = 0; k < lengths.Count; k++) { 
                    lst.Add(new Solution(new decimal[] { lengths[i], lengths[j], lengths[k] })); 
                    for (int l = 0; l < lengths.Count; l++) { 
                        lst.Add(new Solution(new decimal[] { lengths[i], lengths[j], lengths[k], lengths[l] })); 
                    }
                }
            }
        }

        var validSolution = (from sln in lst
                             where sln.Value <= 120.00m
                                && sln.IsValid
                             select sln).OrderByDescending(sln => sln.Value)
                            .First(); 
        Console.WriteLine(validSolution); 
    }

和解决方案类：

public class Solution : IComparable<Solution>
{ 
    public readonly int MaxLengths = 4; 
    public readonly decimal Value; 
    public readonly decimal MaxValue = 120.00m; 
    public readonly bool IsValid;
    public readonly decimal[] Lengths; 

    public Solution(decimal[] lengths)
    { 
        this.Lengths = lengths; 
        if (lengths.Length > 4)
            throw new ArgumentException("Too many lengths."); 
        foreach (var dec in lengths) {
            if (dec <= 0.00m)
                throw new ArgumentException(); 
            Value += dec; 
        }
        IsValid = Value < 120.00m; 
    }       

    public int CompareTo(Solution other)
    {
        if (this.Value > other.Value) return 1; 
        else if (this.Value == other.Value) return 0; 
        else return -1; 
    }

    public override string ToString()
    {
        var value = string.Format("[Solution] Lengths:");
        foreach (var d in Lengths) { 
            value += d + ", "; 
        }
        value += this.Value; 
        return value.ToString(); 
    }
}
于 2013-09-04T00:53:12.407 回答