En iyi boyut kombinasyonunu bulmak için algoritma

Question

İstenen sonucu elde etmek üzere en iyi boyut kombinasyonunu bulmak için bir algoritma arıyorum.

örnek olarak aşağıdaki al:

| 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, ölçülen boyutlarıdır. Ölçülen sonuç y'dir.

Başarmak tüm boyutların kombinasyonları elde etmek istiyorsanız y> = 50 böylece sonuçları olacaktır:

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 

Belki de kolay bir problem ama O açısından optimal bir çözüm anlamaya çalışıyordu (n) ve ben onu bulamadım.

Answer 1

(any, any, ..., any), 0'u içeren bir çalışma kuyruğu ile başlayın. Bu sıradaki elemanlar, bir kombinasyon ve soldaki any değiştirilemeyen birkaç elemandan oluşan çiftler olacaktır (bu daha kısa zamanda daha anlamlı olacaktır). İş kuyruğu boşalana kadar, bir elemanı buradan çıkarın ve karşılık gelen toplamı hesaplayın. Eşiği karşılamıyorsa, atın. Aksi takdirde, istenen kombinasyonlardan biri olarak rapor edin. Değiştirilebilen her bir any için, o sütundaki her bir değer için, any ile değiştirilen geçerli birleşimden oluşan bir kombinasyonun yerini, önceki tüm any değerlerini dizine kilitleyerek.

Çıktıya duyarlı bir sınır göz önünde bulundurulduğunda, bu, en iyi bir polinom faktörü dahilindedir (genelde, üstel olarak birçok kombinasyon olabilir). 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)