Algorithm for finding a combination of the best measurements

Question

I am looking for an algorithm to find the best combination of sizes to achieve the desired result.

As an example, take the following:

| A | B | C | y | |--------|--------|-------|-----| | dog | house1 | green | 30 | | dog | house1 | blue | 15 | | cat | house1 | green | 20 | | cat | house2 | red | 5 | | turtle | house3 | green | 50 | 

A, B, C - measured dimensions. y is the measurement result.

If I want to get all combinations of dimensions that reach y> = 50, so the results will be:

 turtle, house3, green turtle, any, green turtle, house3, any turtle, any, any any, house3, green any, house3, any any, any, green any, house1, green any, house1, any 

This may be an easy problem, but I tried to find the optimal solution in terms of O (n), and I did not find it.

Answer 1

Start with a work queue containing (any, any, ..., any), 0 . The elements of this queue will be pairs consisting of a combination and several elements on the left that cannot be changed with any (this will make sense in the near future). Until the work queue is empty, remove one item from it and calculate the corresponding amount. If it does not meet the threshold, cancel it. Otherwise, report it as one of the desired combinations. For each any that can be changed, for each value in this column it puts a combination of the current one with any replaced by this value, while the index blocks all previous any values.

Given an output-sensitive estimate, this is within the polynomial optimal coefficient (in the general case, there can be exponentially many combinations).

In Python 3:

 def overthreshold(data, threshold): queue = [(('any',) * len(data[0][0]), 0)] for combination, begin in queue: if sum(row[1] for row in data if all(x in {'any', y} for x, y in zip(combination, row[0]))) < threshold: continue yield combination for i in range(begin, len(combination)): if combination[i] == 'any': queue.extend((combination[:i] + (x,) + combination[i+1:], i + 1) for x in {row[0][i] for row in data}) def demo(): data = [ (('dog', 'house1', 'green'), 30), (('dog', 'house1', 'blue'), 15), (('cat', 'house1', 'green'), 20), (('cat', 'house2', 'red'), 5), (('turtle', 'house3', 'green'), 50), ] for combination in overthreshold(data, 50): print(combination)