Вопрос об алгоритме: наиболее подходящие подмножества

Question

Я строю программу, соответствующую сделкам. Ниже приведено описание проблемы, с которой я сейчас сталкиваюсь. Мне нужна помощь с алгоритмами.

Учитывая два набора сделок A и B с похожими атрибутами (дата сделки, счет, символ), мне нужно найти подмножество сделок a в пределах A и b в пределах B, где сумма (a) наиболее близка к сумме (b). Здесь sum () - это сумма определенного атрибута (чистых денег) для этого подмножества. Причина в том, что нам нужно самое близкое совпадение, состоит в том, что если мы не получим идеальное совпадение (идеальный случай), мы хотим следующее самое близкое. примечание: сумма (а) может быть больше или меньше суммы (б).

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

Я чувствую, что это можно сделать с помощью некоторого метода динамического программирования, но я не могу придумать что-то конкретное. Буду признателен за любую помощь.

Answer 1

Эта проблема NP-сложная.

Доказательством является сокращение от подмножества, которое, как известно, является NP-сложным. Для любого экземпляра суммы подмножества, в котором нам дается набор S элементов для суммирования и некоторого целевого числа k, мы можем построить экземпляр вашей задачи, указав в качестве A набор S, а в качестве B - одноэлементный набор {k} , Если мы решим вашу проблему и обнаружим, что самое близкое совпадение не совсем равно k, то мы знаем, что нет способа суммировать подмножество S, чтобы получить k. В противном случае, если есть способ суммировать элементы из S в k, то совпадение будет полностью равно k, и мы знаем, что некоторое подмножество суммируется с целью.

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

Answer 2

Итак, для алгоритма грубой силы мы строим надмножество A и B и строим все их комбинации, суммируем их, строим абсолютную сумму и находим минимум?

sa = superset (A) // () (a) (e) (i) (a, e), (a, i) (e, i) (a, e, i)  
sb = superset (B)

sas = supersetAsums // 0, a, e, i, a+e, a+i, e+i, a+e+i
sbs = supersetAsums

ssas = sorted (sas) 
ssbs = sorted (sbs)

Теперь вы можете перебирать оба списка, если ssas (i)

Проблема здесь заключается в создании подмножеств, которые очень быстро набирают скорость для большинства известных образцов N. :)

Answer 3

Ой, это звучит как subset-sum на стероидах.Было бы неплохо иметь представление о размере вашей проблемы (количество элементов A и B).Проблема, безусловно, будет NP-трудной, поэтому вы не сможете использовать точное решение, такое как приведенное ниже.

Одно простое решение DP - это решение поднабора для A и B отдельно для каждоговозможное значение суммы.Так что если в каждом наборе есть до 10 элементов, которые могут быть между 0 и 50, то для A и B используйте DP, чтобы ответить на вопрос «Есть ли подмножество, которое суммирует в X» для X между 0 и 500. Тогда простопросмотрите два набора и посмотрите, какие значения у них общие, или найдите минимальное расстояние от некоторой возможной суммы в A до некоторой возможной суммы в B.

(Примечание: я сказал «простой», а не «эффективный»'! Но не существует решения, которое было бы значительно быстрее, чем это в терминах Big-O, из-за NP-твердости и т. Д.)