Нахождение подмножества чисел, равного одному числу

Question

Причина, по которой я размещаю это сообщение, заключается в том, что я пытаюсь согласовать счета дебиторской задолженности клиентов, в которых «платежи» размещаются на счетах, а не сопоставляются с открытыми счетами и очищаются. Итак, вот моя проблема:

Иметь один номер (платеж), который должен равняться подмножеству заданного набора номеров (суммы счета). Простой пример:

Оплата $ 10,002

Значения счетов-фактур:

5001 2932 +876 98 21 9923 2069 123 432 765

Я бы хотел вытащить 5001, 2932 и 2069 из этого набора.

Будучи непрограммистом, мне легче всего создать приложение для работы с электронными таблицами Excel. Идеи?

Answer 1

Вы говорите о проблеме NP-Complete, которая называется Subset-sum .

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

Я предполагаю, что если вы хотите изучить N цен, вам придется использовать около 2 ^ N ячеек в Excel для вычисления этого. В статье в Википедии, на которой есть ссылки, приведена некоторая эвристика для аппроксимации этого.

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

Если вы можете найти способ сделать это очень эффективно, возможно, в этом участвует приз .

Answer 2

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