查找最佳尺寸组合的算法
我正在寻找一种算法来找到最佳的维度组合来完成预期的结果。
以下面为例：
| 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是测量的尺寸。 y是测量结果。
如果我想获得所有y> = 50的维度组合，结果如下：
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
也许这是一个简单的问题，但我试图根据O（n）计算出最佳解决方案，但我没有找到它。
从包含(any, any, ..., any), 0的工作队列开始。 这个队列的元素将是由左边的组合和许多元素组成的对，这些元素不能从any变化（这将使得更多的意义很快）。 在工作队列为空之前，从中删除一个元素并计算相应的总和。 如果它不符合阈值，则丢弃它。 否则，请将其报告为寻求的组合之一。 对于每个any可在该列被改变，对于每一个值，入队由当前一个与组合any由值替换，与索引锁定向下所有先前any值。
考虑到输出敏感边界，这是在最优的多项式因子内（通常，可以有指数级的许多组合）。
在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)