C# SolverFoundation는 길이의 최대 조합을 찾습니다.

Question

나는 특정 길이에 가장 적합한 대괄호를 최대 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 해결 방법 솔루션을 엑셀 솔버를 사용하여 1 30.28 "브라켓입니다 , 1 42.09 "브래킷 및 1 46.77"브래킷은 119.14로 나옵니다.

Answer 1

다음은 간단한 솔루션입니다. 나는 또한 수학에 대한 제한된 이해가있다. (가장 진보 된 것은 조합론 등이다.) 그래서 나는 그 도전을 이해한다. 이 솔루션은 모든 가능성을 뛰어 넘고 유효한 솔루션 (전체 길이가 < 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(); 
    } 
}