最適な寸法の組み合わせを見つけるアルゴリズム

Question

私は、望ましい結果を達成するために最良の寸法の組み合わせを見つけるアルゴリズムを探しています。

は、例として以下を取る：

| 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）と私はそれを見つけられませんでした。

Answer 1

(any, any, ..., any), 0を含む作業キューから始めます。このキューの要素は、組み合わせと、左にあるanyから変更できない要素の数からなるペアになります（これはまもなく理解されます）。作業キューが空になるまで、それから1つの要素を削除し、対応する合計を計算します。しきい値を満たしていない場合は、破棄します。それ以外の場合は、それを目的の組み合わせの1つとして報告します。変更可能な各anyについては、その列の各値に対して、anyの現在の値をその値に置き換えて索引を付けて、前のanyの値をすべてロックするエンキューをエンキューします。

出力に敏感な境界を考慮すると、これは最適な多項式係数（一般に指数関数的に多くの組み合わせがあります）にあります。パイソン3において

：ほぼ確実[線形計画（https://en.wikipedia.org/wiki/Linear_programming）に関連

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)