Поиск по списку номеров, суммирующих до суммы в C # - PullRequest
Новая
       15

Поиск по списку номеров, суммирующих до суммы в C #

1 голос
/ 01 февраля 2012

У меня есть пользователь, который вводит набор чисел в диапазоне от 1 до 19 ... и мне нужно найти как можно больше из них, в сумме до 40, каждое число можно использовать только один раз.

Так сказать, список: 19, 17, 11, 13, 8, 9, 7, 5, 10, 16, 14, 8, 7, 3.

Тогда вывод должен быть:
19, 11, 10
16, 14, 7, 3
17, 8, 8, 7

С 13, 9 и 5 оставленными в списке.

Я нашел несколько предложений, но, похоже, они искали только один матч, и я попытался сделать это самостоятельно, но ему все еще не хватает какой-то доработки. 

    private void btnCalc_Click(object sender, RoutedEventArgs e)
    {
        // Copy the list to a new list:
        List<int> lookInto = new List<int>();
        foreach(int i in weaponList)
        {
            lookInto.Add(i);
        }

        int lookFor = 40;
        while (lookFor > 0)
        {
            lookFor = Search(lookInto, lookFor);
        }
        if (lookFor != -1)
        {
            listSell.Items.Add(answer);
        }
    }

    private int Search(List<int> hay, int needle)
    {
        int lowestValue = hay.Min();
        int highestValue = hay.Max();

        if (hay.BinarySearch(needle) > 0)
        {
            int index = hay.BinarySearch(needle);

            if (answer == "")
            {
                answer += hay[index].ToString();
                needle -= hay[index];
                hay.Remove(needle);
            }
            else
            {
                answer += ", " + hay[index].ToString();
                needle -= hay[index];
                hay.Remove(needle);
            }
        }

        if (needle - highestValue > lowestValue || needle - highestValue == 0)
        {
            if (answer == "")
            {
                answer += highestValue.ToString();
                needle -= highestValue;
                hay.Remove(highestValue);
            }
            else
            {
                answer += ", " + highestValue.ToString();
                needle -= highestValue;
                hay.Remove(highestValue);
            }
        }
        else
        {
            for (int i = 0; i > hay.Count; i++)
            {
                if (needle - hay[i] == 0 || needle - hay[i] > lowestValue)
                {
                    if (answer == "")
                    {
                        answer += hay[i].ToString();
                        needle -= hay[i];
                        hay.RemoveAt(i);
                    }
                    else
                    {
                        answer += ", " + hay[i].ToString();
                        needle -= hay[i];
                        hay.RemoveAt(i);
                    }
                }
            }
            if (needle > 0)
            {
                needle = -1;
            }
        }

        return needle;
    }

1 Ответ

0 голосов
/ 15 августа 2013

Я скоро ухожу и не могу набрать фактический блок кода, но вот как вы это сделаете: создайте зеркальный статический массив всех чисел, используйте рекурсивную функцию для перехода и попытайтесь добавить числаот этого массива до достижения 40, если они пройдут 40, он просто вернет -1, иначе все индексы, которые используются для достижения 40, каждый раз, когда он возвращает набор индексов, удаляют эти числа из зеркального массивапоэтому следующая итерация не будет пытаться использовать их и добавлять числа в список множеств.когда рекурсивная функция останавливается, в основном массиве остаются неиспользуемые числа, а список наборов будет содержать все найденные наборы.

Надеюсь, это поможет!

...