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

Question

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

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

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

Answer 1

Think pidgeonhole. Этот метод является сложностью 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_expensive. Перебор элементов, добавляя их во все дыры, чьи правила, которые они удовлетворяют, в результате чего в этих отверстиях:

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