Как быстро определить, удовлетворяет ли какое-либо подмножество этого набора этому условию? - PullRequest
Новая
       31

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

1 голос
/ 12 марта 2012

Я знаю, что это трудная задача для NP, но многие наши пользователи запрашивают эту функцию (в основном, соответствует ли какой-либо набор элементов в вашем текущем заказе одной из заключенных нами сделок? набор предметов в вашем текущем заказе плюс еще один предмет, отвечающий требованиям?)

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

Кто-нибудь имел дело с подобной проблемой, прежде чем он может дать совет?

1 Ответ

2 голосов
/ 12 марта 2012

Подумайте о заглушке. Этот метод имеет O (m + n) сложность для всех случаев.

Объедините каждую «сделку» в набор правил, затем переберите предметы, добавив их в каждую дыру, правила которой они удовлетворяют.

Затем просматривайте сделки, вытаскивая предметы из подоконников, если они там есть.

Пример: 

"blue car", "red car", "yellow expensive car", "red expensive car", "cheap car"

Предложения: 

buy a red car, get a blue car for free
buy an expensive car, get a cheap car for free

«Правила», которые мы можем вывести: 

is_red, is_expensive, is_blue, is_cheap

Итак, у нас есть 2 отверстия: is_red и is_exорого. Проходите по элементам, добавляя их во все отверстия, правила которых они удовлетворяют, и в результате получаются следующие отверстия: 

is_red ( "red car", "red expensive car" )
is_expensive ( "red expensive car", yellow expensive car" )
is_blue ( "blue car" )
is_cheap ( "cheap car" )

Затем пройдитесь по сделкам: 

buy a red car, get a blue car for free
is_red contains "red car", is_blue contains "blue car", so:
    pop them from the holes and make them a deal

Следующая сделка: 

buy an expensive car, get a cheap car for free
is_expensive doesn't contain any cars
...