Как определить, какие числа в наборе складываются с другим заданным числом?

Question

Вот проблема, с которой я, похоже, сталкиваюсь, работая с системой бухгалтерского учета.

У меня есть набор транзакций, но их сумма не равна той сумме, которую бухгалтерия считает необходимой.Они не ставят под сомнение математику, а просто включенные транзакции: p

Существует ли алгоритм, который помог бы мне определить, какие транзакции в наборе не следует включать, чтобы сумма соответствовала заданной сумме?

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

Редактировать: В наборе менее 100 транзакций.Есть ли у кого-нибудь пример C #, поскольку на Решение NP-полной задачи в XKCD вопрос?

Блин, мне следовало получить степень по CS.

Answer 1

Это и есть тот самый Сумма подмножества проблема, которая заключается NP-Полный.Но это не означает, что не существует алгоритма для нахождения суммы подмножеств.

Answer 2

Это и есть тот самый Проблема с Рюкзаком и это NP-Полнота.Вы не сможете легко решить эту проблему с помощью чего-либо, кроме небольших наборов входных данных.Для любого набора задач приличного размера это одна из тех задач, которые нужно решать всю жизнь во вселенной.

Тем не менее, существуют ранцевые решатели на основе генетических алгоритмов.

Answer 3

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

Заданы целые числа [a_1, ...,a_n] и число T,

Определите массив S[i,k] для обозначения того, существует ли подмножество элементов между a_1, ...a_i, которые в сумме равняются k.(Это двоичная матрица).

Затем мы можем определить рекурсивное отношение следующим образом:

S[i,k] = S[i-1,k] или S[i-1,k-a_j]

На словах это означает, что мы либо используем элемент a_i, либо нет.Ответ будет находиться в S[n,T].

Какова рабочая нагрузка для построения матрицы S?Ну, у S есть n * T элементов.Чтобы вычислить каждый элемент, мы должны выполнить O(1) работу.Таким образом, полное время выполнения равно O (n * T).

Теперь, на данный момент, кажется, что я доказал P = NP, поскольку это похоже на алгоритм с полиномиальным временем.Однако помните, что мы измеряем размер входных данных в двоичном формате, поэтому T = 2 ^ p для некоторого p.

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

Кроме того, есть несколько эвристик для решения этой проблемы, но я не эксперт в этой области.

Answer 4

Это версия проблема с рюкзаком.Он NP-полный, так что хорошего общего ответа вы не получите.Насколько велики ваши наборы транзакций?Это 5, как вы показали, или больше похоже на 500?

Answer 5

ОК.Многие люди называли проблему и упоминали , насколько это невероятно сложно .И в целом они правильны.Однако у вас есть очень конкретный случай, который вам нужно решить.Первый вопрос, который следует задать, заключается в том, считаете ли вы, что ваши 100 транзакций близки к тому, чтобы быть правильными.У вас есть некоторый итог ("ваш" итог).У них есть какая-то общая сумма.("реальная" сумма).Таким образом, некоторые из ваших транзакций являются поддельными.Если вы подозреваете, что там всего несколько фиктивных транзакций, то это не так уж плохо.Например, давайте рассмотрим случай, когда существует только одна фиктивная транзакция.В этом случае нам нужно было бы проверить только 100 различных номеров.Если есть 2 фиктивных перехода, то вы смотрите на 100 * 99 проверок, и все пойдет наперекосяк при 4 фиктивных переходах, с почти 100 000 000 шагов.хотя, если все, что вы делаете, это добавляете некоторые значения int, это не так уж и страшно.

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

Answer 6

        bool bBreak = false;
        int iEnd = 13;
        ArrayList ar1 = new ArrayList();
        ar1.Add(2);
        ar1.Add(4);
        ar1.Add(5);
        ar1.Add(7);

        String s1 = " ";
        foreach (int i in ar1)
        {
            if (i == iEnd)
            {
                s1 = "Result = " + i;
                bBreak = true;
            }
            if (bBreak) break;
            ArrayList ar2 = new ArrayList();
            ar2.AddRange(ar1);
            ar2.Remove(i);
            foreach (int j in ar2)
            {
                if ((i + j) == iEnd)
                {
                    s1 = "Results = " + i + ", " + j;
                    bBreak = true;
                }

                if (bBreak) break;
                ArrayList ar3 = new ArrayList();
                ar3.AddRange(ar2);
                ar3.Remove(j);
                foreach (int k in ar3)
                {
                    if (bBreak) break;
                    if ((i + j + k) == iEnd)
                    {
                        s1 = "Results = " + i + ", " + j + ", " + k;
                        bBreak = true;
                    }
                }
            }
        }
        Console.WriteLine(s1);

Answer 7

Да, это возможно.Не уверен, что этот пост все еще открыт.Но вы бы хотели создать надстройку Excel Solver.Запишите все числа, начиная с 1 в соседней ячейке.Затем введите желаемый выходной номер..тогда все используемые числа сохранят свои соседние "1", в то время как неиспользуемые превратятся в "0".Затем выполните формулу фильтра, в которой перечислены только те, рядом с которыми стоит "1".