Проблема суммы подмножества

Как вы должны это делать, зависит от ряда важных вещей: сколько чисел у вас будет и насколько они будут большими? Кроме того, насколько я понимаю, ваши данные могут изменяться (добавлять / удалять числа и т. Д.), Не так ли? Как часто вам нужно делать эти запросы?

Я представлю два решения. Я предлагаю вам использовать второй, поскольку я подозреваю, что он лучше для того, что вам нужно, и его намного легче понять.

Решение 1 - динамическое программирование

Пусть S [i] = true, если мы можем сделать сумму i, и false в противном случае.

S[0] = true // we can always make sum 0: just don't choose any number
S[i] = false for all i != 0
for each number i in your input
    for s = MaxSum downto i
        if ( S[s - i] == true )
            S[s] = true; // if we can make the sum s - i, we can also make the sum s by adding i to the sum s - i.

Чтобы получить фактические числа, составляющие вашу сумму, вы должны оставить другой вектор P [i] = последнее число, которое использовалось для создания суммы i . Вы должны обновить это соответственно в , если условие выше.

Временная сложность этого составляет O (numberOfNumbers * maxSumOfAllNumbers) , что довольно плохо, особенно с учетом того, что вам придется повторно запускать этот алгоритм всякий раз, когда ваши данные меняются.Это также медленно даже для одного запуска, если ваши числа могут быть очень большими, а их может быть много. На самом деле «много» вводит в заблуждение. Если у вас есть 100 чисел, и каждое число может достигать 10 000, вы будете выполнять примерно 100 * 10 000 = 1 000 000 операций при каждом изменении данных.

Это хорошее решение, но оно не очень полезно на практике, по крайней мере, в вашем случае, я думаю.

У него есть C # для подхода, который я предлагаю:

   class Program
      {
        static void Main(string[] args)
        {
            List<int> testList = new List<int>();

            for (int i = 0; i < 1000; ++i)
            {
                testList.Add(1);
            }

            Console.WriteLine(SubsetSum.Find(testList, 1000));

            foreach (int index in SubsetSum.GetLastResult(1000))
            {
                Console.WriteLine(index);
            }
        }
    }

    static class SubsetSum
    {
        private static Dictionary<int, bool> memo;
        private static Dictionary<int, KeyValuePair<int, int>> prev;

        static SubsetSum()
        {
            memo = new Dictionary<int, bool>();
            prev = new Dictionary<int, KeyValuePair<int, int>>();
        }

        public static bool Find(List<int> inputArray, int sum)
        {
            memo.Clear();
            prev.Clear();

            memo[0] = true;
            prev[0] = new KeyValuePair<int,int>(-1, 0);

            for (int i = 0; i < inputArray.Count; ++i)
            {
                int num = inputArray[i];
                for (int s = sum; s >= num; --s)
                {
                    if (memo.ContainsKey(s - num) && memo[s - num] == true)
                    {
                        memo[s] = true;

                        if (!prev.ContainsKey(s))
                        {
                            prev[s] = new KeyValuePair<int,int>(i, num);
                        }
                    }
                }
            }

            return memo.ContainsKey(sum) && memo[sum];
        }

        public static IEnumerable<int> GetLastResult(int sum)
        {
            while (prev[sum].Key != -1)
            {
                yield return prev[sum].Key;
                sum -= prev[sum].Value;
            }
        }
    }

Возможно, вам следует выполнить некоторую проверку ошибок и, возможно, сохранить последнюю сумму в классе, чтобы исключить возможность вызова GetLastResult с сумма, отличная от суммы Найти , с которой последний раз был вызван. Во всяком случае, это идея.

Решение 2 - рандомизированный алгоритм

Теперь это проще. Сохраните два списка: usedNums и unusedNums . Также сохраните переменную usedSum , которая в любой момент времени содержит сумму всех чисел в списке usedNums .

Всякий раз, когда вам нужно вставить число в ваш набор, также добавьте его в один из двух списков (неважно в какой, но делайте это случайным образом, чтобы получилось относительно равномерное распределение). Обновление соответственно использовало сумму .

Всякий раз, когда вам нужно удалить число из вашего набора, выясните, в каком из двух списков оно находится. Вы можете сделать это с помощью линейного поиска, если у вас мало (на этот раз много означает более 10 000, может быть, даже 100 000 на быстром компьютере и при условии, что вы не выполняете эту операцию часто и в быстрой последовательности. В любом случае, линейный поиск можно оптимизировать, если вам это нужно.).Как только вы найдете номер, удалите его из списка. Обновление соответственно использовало сумму .

Всякий раз, когда вам нужно найти числа в вашем наборе, которые суммируются с числом S , используйте этот алгоритм:

while S != usedSum
    if S > usedSum // our current usedSum is too small
        move a random number from unusedNums to usedNums and update usedSum
    else // our current usedSum is too big
        move a random number from usedNums to unusedNums and update usedSum

В конце алгоритма список usedNums ] даст вам числа, сумма которых равна S .

Думаю, этот алгоритм должен быть хорош для того, что вам нужно. Он очень хорошо обрабатывает изменения в наборе данных и хорошо работает для большого количества чисел. Это также не зависит от того, насколько велики числа, что очень полезно, если у вас большие числа.

Если у вас есть вопросы, напишите нам.