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

Question

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

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

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

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

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

Человек, я должен был получить степень CS.

Answer 1

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

Answer 2

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

Тем не менее, есть генетические алгоритмы для решения рюкзаков.

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 для некоторых п.

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

        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);