1

I used this question Find out which combinations of numbers in a set add up to a given total which uses a C# example to attempt to find all the possible combinations of numbers which add up to a given number.

I used the code as provided and have attempted to understand it and I think I do, however, I can't figure out why this error is occurring.

Here is the setup:

public class Program
    {
        public static void Main(string[] args)
        {
            // subtotal list
            List<double> totals = new List<double>(new double[] { 17.5, 14.3, 10.9, 7.8, 6.3, 3.8, 3.2, 2.7, 1.8, 1.0 });
            List<double> totals2 = new List<double>(new double[] { 17.5, 14.3, 7.8, 6.3, 3.2, 1.8});

        // get matches
        List<double[]> results = Knapsack.MatchTotal(50.9, totals2);

        // print results`
        foreach (var result in results)
        {
            Console.WriteLine(string.Join(",", result));
        }

        Console.WriteLine("Done.");
        Console.ReadKey();
    }
}

and the main bulk of the code is unchanged from the example.

public class Knapsack
    {
        internal static List<double[]> MatchTotal(double theTotal, List<double> subTotals)
        {
            List<double[]> results = new List<double[]>();

        while (subTotals.Contains(theTotal))
        {
            results.Add(new double[1] { theTotal });
            subTotals.Remove(theTotal);
        }

        // if no subtotals were passed
        // or all matched the Total
        // return
        if (subTotals.Count == 0)
            return results;

        subTotals.Sort();

        double mostNegativeNumber = subTotals[0];
        if (mostNegativeNumber > 0)
            mostNegativeNumber = 0;

        // if there aren't any negative values
        // we can remove any values bigger than the total
        if (mostNegativeNumber == 0)
            subTotals.RemoveAll(d => d > theTotal);

        // if there aren't any negative values
        // and sum is less than the total no need to look further
        if (mostNegativeNumber == 0 && subTotals.Sum() < theTotal)
            return results;

        // get the combinations for the remaining subTotals
        // skip 1 since we already removed subTotals that match
        for (int choose = 2; choose <= subTotals.Count; choose++)
        {
            // get combinations for each length
            IEnumerable<IEnumerable<double>> combos = Combination.Combinations(subTotals.AsEnumerable(), choose);

            // add combinations where the sum mathces the total to the result list
            results.AddRange(from combo in combos
                             where combo.Sum() == theTotal
                             select combo.ToArray());
        }

        return results;
    }
}

public static class Combination
{
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int choose)
    {
        return choose == 0 ?                        // if choose = 0
            new[] { new T[0] } :                    // return empty Type array
            elements.SelectMany((element, i) =>     // else recursively iterate over array to create combinations
            elements.Skip(i + 1).Combinations(choose - 1).Select(combo => (new[] { element }).Concat(combo)));
    }
}

I have provided the set of numbers which is in totals which are used to try and calculate the total.

I entered 50.9 as the total and return no results.

The second set of numbers totals2 is a set of numbers which add up to 50.9 and they are a subset of totals. This also fails to return a result for 50.9 For some reason the code is unable to find 50.9 in the master set or in the subset (which itself sums to 50.9).

I can't figure out why it does this, can anyone tell me?

DonnellyOverflow
  • 3,981
  • 6
  • 27
  • 39
  • What does the second set add up to according to the computer? double is imperfect – Ňɏssa Pøngjǣrdenlarp Mar 07 '19 at 23:08
  • Please do not provide your entire code, but unly the relevant parts and some sample data. – MakePeaceGreatAgain Mar 08 '19 at 00:40
  • @MakeStackOverflowGoodAgain when debugging it shows it as 50.9 rather than 50.900000000001 or something. I tested it by rounding it with no luck. I also ran it for all numbers between 1 and the sum of the set in increments of 0.1, again rounding and it fines lots, but not 50.9. – DonnellyOverflow Mar 08 '19 at 05:46
  • @HimBromBeere I believe all the code I have provided is necessary to allow for the question to be understood and explored. – DonnellyOverflow Mar 08 '19 at 05:50
  • You should switch to decimal instead of double and try again. I had a similar challenge today and had a similar issue. Switching to decimal fixed it. – Skyqula Mar 08 '19 at 21:05
  • Seems like you should read about floating-point arithmetic. The problem is that `50.9` can´t be loselessly converted to double, it´s rather something like `50.900000001`. This is why float and double should´nt be compared using `==`. – MakePeaceGreatAgain Mar 11 '19 at 07:43

0 Answers0