Алгоритм сопоставления фигур (один ко многим)

Это мой первый пост в stackoverflow.

Мне нужно посоветовать алгоритм финансового приложения. Предположим, у нас есть 2 списка таких цифр (да, это банковские операции):

List 1          | List 2
-------------------------------------
1000            | 200
7000            | 300
3000            | 10000
16000           | 500
                | 16000
                | 4100

Мне нужно сопоставить цифры между собой с учетом некоторых условий:

  1. Совпадения могут быть «один к одному», «один ко многим» или даже «многие ко многим». Итак, здесь два совпадения 16000 (один к одному), 1000 из списка 1 соответствуют 200 + 300 + 500 из списка 2 (один к трем), 10000 из списка 2 соответствуют 7000 + 3000 из списка 1 (один- to-two) и так далее.

  2. Фигурку можно использовать более чем в одном матче.

  3. Количество фигур в двух списках может быть одинаковым, а может и не совпадать.

  4. Максимальное количество фигур в матче «один ко многим» должно быть установлено.

  5. Матчи "многие ко многим" не обязательны. Но было бы хорошо, если бы они были и у нас!

  6. Некоторые цифры могут остаться непревзойденными. Все хорошо.

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

Есть ли лучший алгоритм для этого?


match algorithm financial
person m.zein    schedule 14.02.2013    source источник
comment
Вы можете сэкономить на вычислениях, если сначала отсортируете два списка. Тогда, я полагаю, фигурку можно использовать только один раз за матч? (например, L1: 1000 = 500 + 500: L2 не является допустимым совпадением)   -  person Rerito    schedule 14.02.2013
comment
Что делать, если есть несколько способов составить число? Например, если у вас есть в Списке 2 300, 350, 450, 500 и вам нужно сопоставить 800 в Списке 1. Есть два способа сделать это - как вы определите, какой из них правильный?   -  person RB.    schedule 14.02.2013
comment
Каковы ваши критерии оптимизации? Ясно, что я могу сделать 16000 из 10000 + 4100 + 500 + 500 + 300 + 300 + 300. Вы хотите минимизировать общее количество совпадений? Увеличить количество используемых номеров?   -  person nneonneo    schedule 14.02.2013
comment
@RB - Собственно, моя программа предложит все возможные совпадения для выбранной фигуры на экране.   -  person m.zein    schedule 14.02.2013
comment
@nneonneo - У нас в списках только один 300 и один 500. Таким образом, 16000 не может быть 10000 + 4100 + 500 + 500 + 300 + 300 + 300. Мне нужно оптимизировать время, сохранив функции.   -  person m.zein    schedule 15.02.2013
comment
Фигурку можно использовать более чем в одном матче.   -  person nneonneo    schedule 16.02.2013

Ответы (2)


arrow_upward
3
arrow_downward

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

Это ядро ​​является разновидностью задачи суммы подмножества.

Учитывая это, существуют ограничения на то, насколько лучший алгоритм вы можете найти, и ваши ожидания от поиска «быстрого» алгоритма, вероятно, не оправдаются.

Чтобы сделать ваш алгоритм быстрее, я предлагаю вам начать с сортировки обоих списков. Возьмите первое число из списка 1, из списка 2 возьмите все числа, меньшие или равные числу из списка 1, выясните совпадения, повторите ... Затем перейдите по списку 2 номер за номером ...

person High Performance Mark    schedule 14.02.2013
comment
Что ж, он действительно допускает повторы с обеих сторон. Таким образом, всегда возможно выполнить одно сопоставление "многие ко многим", которое потребляет все значения с обеих сторон, используя их LCM их суммы. Сама проблема может быть несложной, но ее оптимизация по некоторым критериям вполне может оказаться. - person nneonneo; 14.02.2013
comment
Эта проблема немного отличается от проблемы суммы подмножества тем, что она имеет дело только с положительными числами, поэтому сумма всегда будет увеличиваться. Я все еще готов поспорить, что практического решения этой проблемы нет, учитывая несколько сотен чисел, с которыми можно было бы работать. Это может быть не сложно, но все же очень сложно. - person NealB; 14.02.2013
comment
Спасибо за ваши комментарии. Меня заинтересовала проблема суммы подмножества, и я пытаюсь понять ее лучше. - person m.zein; 15.02.2013
comment
@NealB: проблема суммы подмножества имеет две эквивалентные формы: одну для суммирования до 0 и более общую для суммирования до любой целочисленной цели. По сути, это одна и та же проблема, и обе они NP-трудны. - person nneonneo; 16.02.2013
comment
@nneonneo Я не пытался сказать, равна ли сумма нулю или отлична от нуля. Общая проблема суммы подмножества допускает как положительные, так и отрицательные числа, тогда как эта проблема, кажется, имеет дело только с положительными числами. Как только сумма превышает целевое значение, вы можете остановиться, тогда как в случае общей проблемы вы не можете остановиться, потому что может быть какое-то отрицательное число, которое можно использовать для расширения пути поиска. - person NealB; 16.02.2013
comment
@NealB: Неважно! Проблемы одинаково трудны. В лучшем случае вы сэкономите постоянный фактор работы. - person nneonneo; 16.02.2013

arrow_upward
0
arrow_downward

Для этого вы сначала создаете комбинации каждого списка. Например, для списка 1 это следующие комбинации:

1000
3000
7000
16000
1000 3000
1000 7000
1000 16000
3000 7000
3000 16000
7000 16000
1000 3000 7000
1000 3000 16000
1000 7000 16000
3000 7000 16000
1000 3000 7000 16000

Для каждой комбинации вы генерируете сумму элементов в комбинации. Теперь у вас есть два списка сумм. Чтобы решить проблему, вы пересекаете два списка. Существуют различные алгоритмы пересечения. Один из простых подходов - превратить меньший из двух списков в двоичное дерево. Затем для каждого элемента в большом списке вы найдете его в двоичном дереве. Этот алгоритм имеет временную сложность n * log (n).

person Tyler Durden    schedule 14.02.2013
comment
Хмммммм. Интересно! Соответствует ли этот подход указанным требованиям? - person m.zein; 15.02.2013
comment
Я не вижу элемента требований, который не входил бы в объем описываемого мной подхода. Например, если вы хотите ограничить количество фигур в комбинации, это легко, потому что, когда вы генерируете комбинации, как описано выше, обычно это делается по количеству слотов, то есть сначала вы выполняете все комбинации в 1 слоте, а затем вы выполняете все комбинации из 2-х слотов и т. д. Итак, если вы хотите, скажем, максимум 4 фигурки, вы останавливаетесь после выполнения комбинаций из 4-х слотов. - person Tyler Durden; 15.02.2013
comment
Между прочим, парень High Performance понятия не имеет, о чем он говорит. Вы получите довольно разумную производительность с помощью моего метода до 10 000 списков элементов и, возможно, до 100 000. - person Tyler Durden; 15.02.2013