C# SolverFoundation find maximum combination of lengths

Question

I have a list of brackets that I need to find a combination of them up to 4 brackets, that best fits a certain length.

These are my brackets and for example I need to find out what combination of these will be the closest without going over to 120 inches.

<?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>

I've tried to figure out the SolverFoundation library but I'm not a math major and have little experience with it...using the Excel Solver with Simplex LP solving method the solution is 1 30.28" bracket, 1 42.09" bracket, and 1 46.77" bracket which comes out to be 119.14"

Answer 1

Here is a naive solution. I also have a limited understanding of mathematics (most advanced is combinatorics and such!), so I understand the challenge. This solution runs through all possibilities then filters by valid solution (those with total lengths < 120), sorts them by their length, and outputs the first result.

I'm sure that if your solution would require demonstrating understanding of some mathematics concept, this is not the way to go for looking for a solution - but this will allow you to easily check your solution.

The runtime of this is 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); 
    }

And the Solution class:

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