-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 ライブラリを理解しようとしましたが、私は数学専攻ではなく、ほとんど経験がありません...シンプレックス LP 解法で Excel ソルバーを使用すると、解は 1 30.28 インチのブラケット、1 42.09 インチのブラケット、および119.14インチになる46.77インチブラケット1個。

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 に答える