Подбор чисел из массивов для получения нужной суммы

/*
 * Сделано в SharpDevelop.
 * Пользователь: Михто
 * Дата: 27.03.2014
 * Время: 14:46
 *
 * Для изменения этого шаблона используйте Сервис | Настройка | Кодирование | Правка стандартных заголовков.
 */
using System;
using System.Collections.Generic;
using System.Windows.Forms;
using System.IO;
using System.Threading;
 
namespace Load
{
 
 
    /*
     * есть 2 (любое число) массива чисел. нужно получить 2 (любое число) определенные суммы из этих чисел, обязательно (опционально) из обоих массивов.
     * для этого класс числа имеет свойство - к какому массиву он относится.
     *
     * алгоритм - рекурсивный перебор в ширину. то есть дерево с 1 вершиной.
     *
     * 
     * 1. создаем объект-обработчик. каждый объект будет представлять свой пусть вычислений.
     * 
     * у каждого из объектов-обработчиков есть 
     * - список всех исходных чисел - все числа из обих массивов
     * - список использовавшихся чисел 
     * - список вариаций использовавшихся чисел
     *
     * 2. перебираем все исходные числа, текущее i.
     * 3. создаем объект-обработчик, в котором удаляем i из списка исходных, добавляем i в список использовавшихся
     * 4. находим сумму всех использовавшихся чисел. если сумма +- погрешность больше искомой суммы, гоу 2.
     * 5. если использовавшиеся числа уже были, но в другом порядке, гоу 2   
     * 
     * 6. если сумму всех использовавшихся чисел +- погрешность равна 0, то нужная последовательность чисел найдена
     * 7. мы ее проверяем, есть ли в списке использовавшихся числа из обоих массивов. если есть - то переходим к поиску второй суммы, гоу 2.
     * 
     * 8. если сумму всех использовавшихся чисел +- погрешность не равна 0, продолжаем поиски. гоу 2.
     *
     *
     *
     */
 
 
    // класс чисел
    // содержит только значение числа и номер массива
    public class cNumber
    {
        // значение
        public double Value
        {
            get;
            private set;
        }
 
        // номер массива
        public int NumberArray
        {
            get;
            private set;
        }
        public int NumberRow
        {
            get;
            private set;
        }
 
 
        public cNumber(double _Value, int _NumberArray, int _NumberRow)
        {
            Value = _Value;
            NumberArray = _NumberArray;
            NumberRow = _NumberRow;
 
        }
 
    }
 
 
    // класс обработки чисел
    // каждый класс представляет ветвь вычислений
    public class cNumberProcess
    {
        public bool flag;
        // содержит решения
        public static List<cNumberProcess> RightSolutions = new List<cNumberProcess>();
 
        public static List<cNumber> lstDFO;
 
        // все ранее использовавшиеся числа
        // проверка IsAlreadyUsed
        List<string> AlreadyUsed = new List<string>();
 
 
        // просто счетчик
        public static double counter = 0;
 
        // список искомых сумм
        List<double> lstNeededSum;
        // номер в списке суммы, которую ищем сейчас
        double SumIndex;
 
        // требуемая сумма
        public double NeededSum
        {
            get
            {
                return lstNeededSum[int.Parse(SumIndex.ToString())];
            }
        }
 
        // максимальная погрешность
        public double ErrorValue;
 
        // сумма использовавшихся чисел
        public double SumUsed
        {
            get
            {
                double sumUsed = 0;
                foreach (var i in lstUsed)
                {
                    sumUsed += i.Value;
 
                }
                return sumUsed;
            }
        }
 
        // разница
        public double Difference
        {
            get
            {
                return (NeededSum - SumUsed);
 
            }
        }
 
        // если разница примерно равна 0, в пределах +- погрешности
        bool IsSumFounded
        {
            get
            {
                return (Math.Abs(Difference) <= ErrorValue);
            }
        }
 
        // если разница + погрешность меньше нуля, то ничего хорошего уже не случится. пора прекращать.
        bool IsVeryMuch
        {
            get
            {
                return ((Difference + ErrorValue) < 0);
            }
        }
 
        // использовались числа всех массивов?
        bool IsAllArrays
        {
            get
            {
                // находим число использовавшихся массивов
                List<int> lstArrayUsed = new List<int>();
                foreach (var i in lstUsed)
                {
                    if (!lstArrayUsed.Contains(i.NumberArray)) lstArrayUsed.Add(i.NumberArray);
                }
 
 
 
 
                // находим число исходных массивов
                // надо учесть, что из исходных массивов числа перемещены в список использовавшихся
                List<int> lstArraySource = new List<int>();
                foreach (var i in lstSource)
                {
                    if (!lstArraySource.Contains(i.NumberArray)) lstArraySource.Add(i.NumberArray);
                }
 
 
                foreach (var prev in lstPreviousSolutions)
                {
                    foreach (var i in prev.lstUsed)
                    {
                        // if (!lstArrayUsed.Contains (i.NumberArray )) lstArrayUsed.Add (i.NumberArray );
                        if (!lstArraySource.Contains(i.NumberArray)) lstArraySource.Add(i.NumberArray);
                    }
 
                }
 
                // если использовано массивов меньше, чем осталось, это однозначно фэил
                if (lstArrayUsed.Count < lstArraySource.Count)
                    return false;
 
                // если нет хоть одного массива, это фэил
                foreach (var i in lstArraySource)
                {
                    if (!lstArrayUsed.Contains(i)) return false;
                }
 
                return true;
 
 
            }
        }
        // список исходных
        List<cNumber> lstSource;
 
        // список использовавшихся
        public List<cNumber> lstUsed;
 
        // давно использовавшихся
        public List<cNumberProcess> lstPreviousSolutions = new List<cNumberProcess>();
 
        public cNumberProcess(List<double> _NeededSum, double _SumIndex, double _ErrorValue, List<cNumber> _lstSource, List<cNumber> _lstUsed, List<cNumberProcess> _lstPreviousSolutions, List<string> _AlreadyUsed, bool _flag)
        {
            flag = _flag;
            lstNeededSum = _NeededSum;
            SumIndex = _SumIndex;
            ErrorValue = _ErrorValue;
            lstSource = new List<cNumber>(_lstSource);
            lstUsed = new List<cNumber>(_lstUsed);
            lstPreviousSolutions = new List<cNumberProcess>(_lstPreviousSolutions);
            AlreadyUsed = _AlreadyUsed;
 
 
        }
 
 
 
        // страшная проверка
        // чтобы глупый комп не считал что "2, 3" и "3, 2" это разные наборы чисел
        bool IsAlreadyUsed()
        {
            // берем использовавшиеся числа
            var lst = new List<cNumber>(this.lstUsed);
 
            // сортируем их
            lst.Sort((a, b) =>
                     a.Value.CompareTo(b.Value));
 
            // переводим в строку
            string used = "";
            foreach (var i in lst)
            {
                used += i.Value.ToString() + "_" + i.NumberArray.ToString() + " ";
            }
 
            // строку ищем в списке
            bool res = AlreadyUsed.Contains(used);
            if (!res)
            {
                AlreadyUsed.Add(used);
            }
            return res;
        }
        Thread th;
        public void Tered()
        {
            th = new Thread(new ThreadStart(Recoursive));
            th.Start();
 
 
 
        }
 
        public void ShowcNumber(cNumberProcess _x)
        {
            lstDFO = new List<cNumber>();
 
            foreach (var j in _x.lstPreviousSolutions)
            {
 
                foreach (var k in j.lstUsed)
                {
                    lstDFO.Add(k);
                   
                }
            }
          
        }
        
        public static bool flagg;
        // рекурсивный метод
        public void Recoursive()
        {
            // перебираем все входные значения
            foreach (var i in this.lstSource)
            {
                if (this.flag == true)
                    break;
                cNumberProcess x = new cNumberProcess(lstNeededSum, SumIndex, ErrorValue, lstSource, lstUsed, lstPreviousSolutions, AlreadyUsed, false);
 
                x.lstSource.Remove(i);
                x.lstUsed.Add(i);
 
                // сумма чисел уже слишком большая
                if (x.IsVeryMuch)
                    continue;
 
                // данные числа уже использовались, но в других сочетаниях
                if (x.IsAlreadyUsed())
                    continue;
 
                // нашли последовательность
                // и используются элементы всех массивов
                if (x.IsSumFounded && x.IsAllArrays)
                //                if (x.IsSumFounded)
                {
 
                    // сохраняем это решение и будем искать дальше
                    x.lstPreviousSolutions.Add(new cNumberProcess(x.lstNeededSum, x.SumIndex, x.ErrorValue, x.lstSource, x.lstUsed, new List<cNumberProcess>(), new List<string>(), false));
 
                    double _SumIndex = x.SumIndex;
                    _SumIndex++;
 
                    // если больше нечего искать
                    if (_SumIndex >= x.lstNeededSum.Count)
                    {
                        // сохраняем решение в статичный массив
                        cNumberProcess.RightSolutions.Add(x);
                        ShowcNumber(x);
                        Stavka stavka = new Stavka();
                        flagg = false;
                        while (!flagg)
                        {
                            System.Threading.Thread.Sleep(100);
                        }
 
                        return;
                    }
                    else
                        // еще есть что искать
                        x.SumIndex++;
 
 
                    // обнуляем массив использовавшихся
                    x.lstUsed = new List<cNumber>();
                    x.AlreadyUsed = new List<string>();
                    if (flag != true)   // и ищем
                        x.Recoursive();
                }
 
                if (flag != true)  // ищем!
                    x.Recoursive();
 
            }
 
        }
    }
}