CODEWITHSUNDEEP
algorithmcomputer-sciencesubsetsubset-sum
Drew
Drew

Reputation: 13398

How to quickly tell if any any subset of this set satisfy this condition?

I know this is an NP-hard problem, but a lot of our users have been requesting this feature (basically, does any set of the items in your current order qualify for one of the deals we have running? Or does any set of the items in your current order plus one other item qualify?)

Since providing the functionality is more about user convenience than finding the correct answer I've been considering shortcuts to do this without taking too long, such as not running the algo if there are more than X items, where X is the number that causes noticeable lag, or only running the most recently added X items through the algorithm.

Has anyone dealt with a similar issue before that can offer advice?

Upvotes: 1

Views: 100

Answers (1)

DanRedux
DanRedux

Reputation: 9349

Think pidgeonhole. This method is O(m+n) complexity for all cases.

Combine each "deal" into a set of rules, then loop through the items, adding them to each pidgeonhole whose rule they satisfy.

Then loop through the deals, pulling items from the pidgeonholes if they are in there.

Example:

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

The deals:

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

The "rules" we can deduce:

is_red, is_expensive, is_blue, is_cheap

So we have 2 holes, is_red and is_expensive. Loop through the items, adding them to all the holes whose rules they satisfy, resulting in these holes:

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

Then loop through the deals:

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

The next deal:

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

Upvotes: 2

Related Questions